Branch-and-Cut for Nonconvex Quadratic Programming
Dieter Vandenbussche, University of Illinois at Urbana-Champaign
We present a branch-and-cut algorithm for bound-constrained QP's based on a
classic reformulation of QP as a linear program with complementarity
constraints. By characterizing the convex hull of a subset of the
constraints, we obtain a class of cutting planes that can be easily
separated. We incorporate these into a branch-and-cut algorithm and discuss
some computational results. We also discuss the use of the reformulation
for some types of mixed integer nonconvex quadratic programs and develop
polyhedral results for this case.
Chemnitz Workshop
Last modified: Thu Nov 11 17:50:21 CET 2004