Features of the MIP optimizer for MIQCP
Specifies features of the MIP optimizer that are relevant to mixed integer quadratically constrained programs (MIQCP).
Solving a mixed integer quadratically constrained program (MIQCP) can introduce special considerations with respect to the branch and bound search. Some MIQCP models lend themselves to solution as a second order cone program. In other MIQCP models, outer approximation can be a useful strategy. Special considerations about cuts can also apply to some MIQCP models.
SOCP branch and bound or outer approximation?
CPLEX solves most MIQCP models roughly in the same way as it solves other mixed integer programs (MIP). However, CPLEX offers algorithmic options adapted to the nonlinearity of the quadratic constraints in a MIQCP model. Indeed, CPLEX offers two main search strategies to solve a MIQCP model.
- One strategy exploits a branch and bound search tree based on the continuous QCP solver. For more information about the QCP solver, see Solving problems with quadratic constraints (QCP).
- Another strategy exploits outer approximation relying on the continuous LP solver to build a search tree.
To choose between these two strategies, the user sets the MIQCP strategy switch, as documented in the reference manual Parameters of CPLEX.
In the branch and bound strategy based on the QCP solver, CPLEX develops a search tree and solves the continuous relaxation of the model by the SOCP solver at each node of the tree. That is, at each node of the tree, all quadratic constraints are satisfied.
In the outer approximation strategy, CPLEX builds a linear approximation of the model by using first order approximations of the quadratic constraints. These linear approximations are refined throughout the algorithm to yield an optimal solution that satisfies all the quadratic constraints of the model. The linear approximation cuts are known as cone linearizations.
By default, CPLEX tries to choose the best of the two strategies. However, you may have knowledge of your model that implies that one of the two strategies is more appropriate. In that case, you can choose the strategy manually to yield better results.
Usually, the branch and bound strategy based on the QCP solver has the advantage of obtaining tighter bounds at the nodes; these tighter bounds at the nodes can cost much more time to process each node.
In contrast, the outer approximation strategy based on the LP solver has the advantage of processing nodes faster, but the relaxations in this strategy can be weaker.
On some numerically challenging models, one strategy can be more robust than the other.
Cuts and MIQCP
All the cuts available in CPLEX to solve a mixed integer program (MIP) are also available to solve a MIQCP. For more about MIP cuts, see Cuts in this manual.
Cone cuts are separated automatically, depending on the strategy used to solve MIQCPs.
Lift-and-project cuts can be useful in solving some MIQCP models. See documentation of the parameter Lift-and-project cuts switch for MIP and MIQCP in the CPLEX Parameters Reference Manual.