Introduction

The Global Mixed-Integer Quadratic Optimizer, GloMIQO (Gló-me-ko), considers Mixed-Integer Quadratically-Constrained Quadratic Programs MIQCP of the form [181, 182, 187] :

\[ \begin{array}{rl} \tag{MIQCP} \min \; & x^T \cdot Q_0 \cdot x + a_0 \cdot x \\[8pt] \text{s.t. } & b_m^{\mathrm{LO}} \leq x^T \cdot Q_m \cdot x + a_m \cdot x \leq b_m^{\mathrm{UP}} \quad \forall \; m \in \{ 1, \, \ldots, \, M \} \\[8pt] & x \in \mathbb{R}^{C} \times \left\{ 0, \, 1 \right\}^{B} \times \mathbb{Z}^{I} \\ \end{array} \]

where \(C\), \(B\), \(I\), and \(M\) represent the number of continuous variables, binary variables, integer variables, and constraints, respectively. Note that this model can address quadratic continuous and/or integer terms, as well as bilinear terms of continuous-continuous, integer-continuous, and integer-integer type. We assume that it is possible to infer finite bounds \(\left[ x_i^L, \, x_i^U \right]\) on the variables participating in nonlinear terms.

Major applications of MIQCP include quality blending in process networks, separating objects in computational geometry, and portfolio optimization in finance. Specific instantiations of MIQCP in process networks optimization problems include: pooling problems [6, 12, 20, 34, 90, 120, 128, 130, 155, 178, 179, 180, 185, 186, 196, 252, 261] , distillation sequences [9, 91, 94], wastewater treatment and total water systems [11, 13, 22, 35, 79, 103, 134, 137, 197, 201] , hybrid energy systems [23, 24, 77] , heat exchanger networks [58, 93] , reactor-separator-recycle systems [147, 148] , separation systems [223] , data reconciliation [211] , batch processes [163] , and crude oil scheduling [157, 159, 160, 189, 188] . Computational geometry problems formulated as MIQCP include: point packing [17, 60] , cutting convex shapes from rectangles [136, 202] , maximizing the area of a convex polygon [19, 21] , and chip layout and compaction [73] . Portfolio optimization in financial engineering can also be formulated as MIQCP [173, 205] .

As illustrated in the following figure, GloMIQO responds dynamically to elucidate and exploit special structure within MIQCP. GloMIQO falls broadly into the category of branch-and-bound global optimization because it: generates and solves convex relaxations of the nonconvex MIQCP that rigorously bound the global solution, finds feasible solutions via local optimization, and divides and conquers the feasible set to generate a sequence of convex relaxations converging to the global optimum [95, 92] .

Given a MIQCP optimization problem, GloMIQO reformulates the model, detects special structure in the reformulated MIQCP, solves the optimization problem, and returns the model with respect to the original problem variables

Licensing and software requirements

Using GAMS/GloMIQO requires

a GloMIQO or ANTIGONE license,
a CPLEX license, and
a CONOPT or SNOPT license.

GloMIQO may stand alone as a MIQCP solver; it is also available as a proper subset of the general MINLP solver ANTIGONE and is included with a GAMS/ANTIGONE license.

Running GAMS/GloMIQO

GAMS/GloMIQO solves MIQCP, RMIQCP, and QCP models. If GAMS/GloMIQO is not the default solver for these models, it can be called using the following command before the solve statement:

option miqcp=glomiqo, rmiqcp=glomiqo, qcp=glomiqo;

GloMIQO Options

The GloMIQO options match the GAMS/ANTIGONE options.

GloMIQO Algorithmic Features

As illustrated in the figure above, the primary algorithmic features in GloMIQO are reformulating model input, elucidating special structure, and branch-and-bound global optimization [181, 182, 187] .

Reformulating Model Input

While the transformation steps illustrated in the following figure, are implemented generically and applied universally, the reformulations are specifically targeted at enhancing the performance of GloMIQO on process networks problems. GloMIQO effectively transforms modular process networks problems into generalized pooling problems [179, 182] . GloMIQO may also add nonconvex bilinear terms to the model formulation to generate tight Reformulation-Linearization Technique cuts.


(a) Original Model	(b) Variable Elimination	(c) Disaggregation

(a) Process networks problems are typically defined as a series of modular units. (b) The GloMIQO variable elimination steps transform the user model. (c) The subsequent bilinear term disaggregation further reformulates the model. The entire process is seamless and unseen by the modeler; GloMIQO reverses all transformations after solving the problem and reports results with respect to the original model in (a).

Elucidating Special Structure

GloMIQO automatically detects: (a) Reformulation-Linearization Technique (RLT) equations that do not add nonlinear terms to MIQCP and (b) special structure in separable multivariable terms [182] .

GloMIQO considers equation/variable and equation/equation products for generating cuts and improving variable bounding. These RLT equations are updated at every node of the branch-and-bound tree:

Equation/Variable: Products of variable \(x_i\) with linear equation \(m\) (e.g., \(\left[ a_m \cdot x - b_m^{\mathrm{UP}} \right] \cdot \left[ x_i - x_i^{\mathrm{LO}} \right] \leq 0\))

Equation/Equation: Products of two linear equations \(m, \, n\) (e.g., \(-1 \cdot \left[ a_m \cdot x - b_m^{\mathrm{UP}} \right] \cdot \left[ a_n \cdot x - b_n^{\mathrm{UP}} \right] \leq 0\))

The GloMIQO preprocessor will add particularly strong RLT cuts outright the the model formulation. Modelers will significantly improve the performance of GloMIQO by writing linear constraints that can be multiplied together without increasing the number of nonlinear terms.


(a) Undirected Graph Representation	(b) Separable Multivariable Terms	(c) Low-Dimension Edge-Concave Aggregations

(a) A Nonlinear equation m is an undirected graph with nodes representing variables and edges representing nonzero coefficients Q_{m, i, j}; (b) The equation is divided into separable multivariable terms by detecting disjoint vertex sets. (c) Separable multivariable terms are sum decomposable, so all high-order cuts and every bounding strategy operates on a specific multivariable term. For example, detecting three-dimensional edge-concave aggregations is illustrated in red.

As depicted in the figure above, GloMIQO generates an undirected graph representation of each individual nonlinear equation \(m\), partitions the equation into separable multivariable terms, and detects special structure including convexity and edge-concavity in the individual multivariable terms [182] .

Branch-and-Bound Global Optimization

GloMIQO falls broadly into the category of branch-and-bound global optimization because it: generates and solves convex relaxations of the nonconvex MIQCP that rigorously guarantee lower bounds on the global solution, finds feasible solutions via local optimization to bound the global solution from above, and divides and conquers the feasible set to generate a sequence of convex relaxations converging to the global optimum [95, 92] .

GloMIQO generates convex relaxations using: termwise McCormick envelopes, low-dimensional edge-concave relaxations, eigenvector projections, piecewise-linear underestimators, outer approximation cuts for convex terms, and an adaptive implementation of the Reformulation-Linearization Technique (RLT) [120, 180, 181, 182, 187, 185, 186] .

GloMIQO dynamically tightens convex relaxations with cutting planes derived from edge-concave aggregations, \(\alpha\)BB underestimators, and convex terms. Cuts are based on both individual equations and the collection of bilinear terms in MIQCP . The branch-and-cut strategies differentiate globally-valid \(\alpha\)BB and convex cuts from locally-valid edge-concave cuts. Previously-generated cuts are saved in a pool and applied as appropriate in the branch-and-bound tree.

GloMIQO searches for feasible solutions by multistarting an NLP solver.

GloMIQO reduces the search space using reliability branching, feasibility-based bounds tightening, optimality-based bounds tightening, RLT-based bounds tightening, and bounds tightening based on all higher-order cuts [181, 182, 187] .

Table of Contents