CRPC-TR99783-S						January 1999

Title: A Branch and Cut Algorithm for Nonconvex Quadratically Constrained
Quadratic Programming

Authors: Charles Audet, Pierre Hansen, Brigitte Jaumard, and Gilles Savard

Submitted January 1999

Abstract:
We present a branch and cut algorithm that yields in finite time, a
globally E-optimal solution (with respect to feasibility and optimality)
of the nonconvex quadratically constrained quadratic programming problem.
The idea is to estimate all quadratic terms by successive linearizations
within a branching tree using Reformulation-Linearization Techniques 
(RLT). To do so, four classes of linearizations (cuts), depending on one
to three parameters, are detailed. For each class, we show how to select
the best member with respect to a precise criterion. The cuts introduced
at any node of the tree are valid in the whole tree, and not only within
the subtree rooted at that node. In order to enhance the computational
speed, the structure created at any node of the tree is flexible enough to
be used at other nodes. Computational results are reported. Some problems
of the literature are solved, for the first time with a proof of global
optimality.

Key words: Nonconvex programming, quadratic programming, RLT,
linearization, outer-approximation, branch and cut, global optimization.

------------------------------------------------------------------------------
Charles Audet
charlesa@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University

Pierre Hansen
Departement MQ
GERAD and Ecole des Hautes Etudes Commerciales

Brigitte Jaumard	Gilles Savard
Departement de Mathematiques et de Genie Industriel
GERAD and Ecole Polytechnique de Montreal