Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2

Abstract

The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to ε-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation–linearization technique equations, convex multivariable terms, αBB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Crama's [Concave extensions for nonlinear 0-1 maximization problems, Math. Program. 61 (1993), pp. 53–60] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.

Keywords:

• quadratically constrained quadratic programming
• cutting planes
• global optimization

AMS Subject Classifications::

• 90C26
• 90C20
• 90C57
• 65K05

Funding

C.A.F. is thankful for support from the National Science Foundation [CBET–0827907]; National Institutes of Health [R01 GM052032]. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship to R.M. [grant no. DGE-0646086] and by a Royal Academy of Engineering Research Fellowship awarded to R.M. J.B.S. was supported by the National Institutes of Health Grants [P50GM071508-06 and R01 GM052032].