MIQCP: mixed integer programs with quadratic terms in the constraints

Distinguishes types of mixed integer quadratically constrained programs according to quadratic terms in the constraints of the model.

As introduced in the topic Stating a MIP problem, a mixed integer programming (MIP) problem can contain both integer and continuous variables. If the problem contains an objective function with no quadratic term, (a linear objective), and all the constraints are linear, then the problem is termed a Mixed Integer Linear Program (MILP).

If there is a quadratic term in the objective function and all the constraints in the model are linear, the problem is termed a Mixed Integer Quadratic Program (MIQP). (For more information about solving a MIQP, see the topic MIQP: mixed integer programs with quadratic terms in the objective function.) If the model has any constraints containing a quadratic term, regardless of the objective function, the problem is termed a Mixed Integer Quadratically Constrained Program (MIQCP).

This topic explores MIQCP further and specifies the features of MIQCP problems that CPLEX solves.

The topics Characteristics of a quadratically constrained program and Convexity clarify the difference between convex and nonconvex quadratically constrained programs (QCP). That same distinction is relevant to MIQCP problems as well.

By default, CPLEX can solve a mixed integer quadratically constrained program (MIQCP) satisfying certain conditions on the objective function and on the constraints.

Conditions on the objective function

• The objective function is linear.
• Or, the objective function contains quadratic terms and is convex. The observations in Distinguishing between convex and nonconvex QPs apply here.
• Or, the objective function contains only quadratic terms that are the product of binary variables; in this case, the objective function is not necessarily convex.

Conditions on the constraints

Each constraint in the MIQCP model must be an inequality. Furthermore, each of those inequality constraints must satisfy at least one of the following conditions:

• The constraints that contain a quadratic term can be represented as second order cone programs (SOCP). The topics Characteristics of a quadratically constrained program and Convexity are also relevant here.
• The quadratic term in a constraint involves only multiplication of binary variables.

If these assumptions about the objective and about the constraints are not satisfied, CPLEX will return the error CPXERR_Q_NOT_POS_DEF.