Globally optimizing mixed-integer quadratically-constrained quadratic programs

Major applications of mixed-integer quadratically-constrained quadratic programs (MIQCQP) include quality blending in process networks, separating objects in computational geometry, and portfolio optimization in finance. Specific instantiations of MIQCQP in process networks optimization problems include: pooling problems, distillation sequences, wastewater treatment and total water systems, hybrid energy systems, heat exchanger networks, reactor-separator-recycle systems, separation systems, data reconciliation, batch processes, crude oil scheduling, and natural gas production. Computational geometry problems formulated as MIQCQP include: point packing, cutting convex shapes from rectangles, maximizing the area of a convex polygon, and chip layout and compaction. Portfolio optimization in financial engineering can also be formulated as MIQCQP. MIQCQP is mathematically defined:

where C, B, I, and M represent the number of continuous variables, binary variables, integer variables, and constraints, respectively. We assume that it is possible to infer finite bounds on the variables participating in nonlinear terms.

GloMIQO (Global Mixed-Integer Quadratic Optimizer; 1, 2) is a numerical solver addressing MIQCQP to ε-global optimality. GloMIQO is available through Princeton University and GAMS.

The aggregate performance profiles [Dolan and Moré] for the complete test suite diagrammed in the figures display a strong advantage for GloMIQO across a wide array of problem classes:

TimePercent gap remaining

GloMIQO is the fastest solver for ≈ 48% of the test cases and can address ≈ 70% of the test cases within the time limit. Additionally, GloMIQO generally closes more of the optimality gap. The success of GloMIQO is a direct result of finding and exploiting an array of special structure components within MIQCQP.