What does CPLEX solve?

Explains what is solved in terms of problem types.

Given an active model, CPLEX solves one continuous relaxation or a series of continuous relaxations.

  • A single LP is solved if IloCplex.isMIP, IloCplex.isQO, and IloCplex.isQC return false. This is the case if the active model does not include:

  • A single QP is solved if both IloCplex.isMIP and IloCplex.isQC return false and IloCplex.isQO returns true. This is the case if the active model contains a quadratic (and positive semi-definite) objective but does not contain:

    • integer variables, Boolean variables, or semi-continuous variables;

    • quadratic terms among the constraints;

    • special ordered sets; or

    • piecewise linear functions among the constraints.

      As in the case of LPs, IloCplex provides several optimizing algorithms to solve QPs. For more about identifying this kind of problem, see Solving problems with a quadratic objective (QP).

  • A single QCP is solved if IloCplex.isMIP returns false and IloCplex.isQC returns true, indicating that it detected a quadratically constrained program (QCP). This is the case if the active model contains one or more quadratic (and positive semi-definite) constraints but does not contain:

    • integer variables, Boolean variables, or semi-continuous variables;

    • special ordered sets; or

    • piecewise linear functions.

      IloCplex solves QCP models using the barrier optimizer. For more about this kind of problem, see Solving problems with quadratic constraints (QCP), where the special case of second order cone programming (SOCP) problems is also discussed.

In short, an LP model has a linear objective function and linear constraints; a QP model has a quadratic objective function and linear constraints; a QCP includes quadratic constraints, and it may have a linear or quadratic objective function. A problem that can be represented as LP, QP, or QCP is also known collectively as a continuous model or a continuous relaxation.

A series of relaxations is solved if the active model is a MIP, which can be recognized by IloCplex.isMIP returning true. This is the case if the model contains any of the objects excluded for single continuous models. If a MIP contains a purely linear objective function, (that is, IloCplex.isQO returns false ), the problem is more precisely called an MILP. If it includes a positive semidefinite quadratic term in the objective, it is called an MIQP. If it includes a constraint that contains a positive semidefinite quadratic term, it is called an MIQCP. MIPs are solved using branch & cut search, explained in more detail in Solving mixed integer programming problems (MIP).