Solving the extracted model with ILOG CPLEX involves solving one or a series of continuous relaxations:
-
Only one continuous relaxation needs to be solved if the extracted model is continuous itself, that is, if it does not contain integer variables, Boolean variables, semi-continuous or semi-integer variables, logical constraints, special ordered sets (SOS), or piecewise linear functions. Solving LPs: Simplex Optimizers and Solving LPs: Barrier Optimizer discuss the algorithms available for solving LPs. Similarly, Solving Problems with a Quadratic Objective (QP), discusses the algorithms available for solving QPs. Solving Problems with Quadratic Constraints (QCP) re-introduces the barrier optimizer in the context of quadratically constrained programming problems (QCPs). Using Piecewise Linear Functions in Optimization: a Transport Example introduces piecewise-linear functions through a transportation example. Logical Constraints in Optimization introduces logical constraints, and chapters following it offer examples.
-
In all other cases, the extracted problem that ILOG CPLEX sees is indeed a MIP and, in general, a series of continuous relaxations needs to be solved. The method
cplex.isMIP
returns IloTrue
in such a case. Solving Mixed Integer Programming Problems (MIP) discusses the algorithms applied.
The optimizer option used for solving the first continuous relaxation (whether it is the only one or just the first in a series of problems) is controlled by setting the root algorithm parameter:
cplex.setParam(IloCplex::RootAlg, alg);
where alg
is a member of the nested enumeration IloCplex::Algorithm
.
As a nested enumeration, the fully qualified names that must be used in the program are IloCplex::Primal
, IloCplex::Dual
, and so on. Table 1.2 displays the meaning of the optimizer options defined by IloCplex::Algorithm.
The choice Sifting
is not available for QP models. Only the Barrier
option is available for QCP models. Table 1.3 summarizes these options.
Table 1.2 Optimizer Options in IloCplex::Algorithm
IloCplex::AutoAlg |
let CPLEX decide which algorithm to use |
|
use the primal simplex algorithm |
|
use the dual simplex algorithm |
|
use the primal network simplex algorithm on an embedded network followed by the dual simplex algorithm for LPs and the primal simplex algorithm for QPs on the entire problem |
|
use the barrier algorithm. The type of crossover performed after the barrier algorithm is set by the parameter IloCplex::BarCrossAlg . |
|
use the sifting algorithm |
|
use multiple algorithms concurrently on a multiprocessor system |
Table 1.3 Algorithm Available at Root by Problem Type
Value |
Algorithm Type |
LP?
MILP? |
QP?
MIQP? |
QCP?
MIQCP? |
0 |
IloCplex::AutoAlg |
yes |
yes |
yes |
1 |
IloCplex::Primal |
yes |
yes |
not available |
2 |
IloCplex::Dual |
yes |
yes |
not available |
3 |
IloCplex::Network |
yes |
yes |
not available |
4 |
IloCplex::Barrier |
yes |
yes |
yes |
5 |
IloCplex::Sifting |
yes |
not available |
not available |
6 |
IloCplex::Concurrent |
yes |
yes |
not available |
If the extracted model requires the solution of more than one continuous relaxation, the algorithm for solving the first one at the root is controlled by the RootAlg
parameter. The algorithm at all other nodes except the root is controlled by the NodeAlg
parameter:
cplex.setParam(IloCplex::NodeAlg, alg).
Table 1.4 summarizes the options available at nodes.
Table 1.4 Algorithm Types for NodeAlg
Value |
Algorithm Type |
MILP? |
MIQP? |
MIQCP? |
0 |
IloCplex::Auto |
yes |
yes |
yes |
1 |
IloCplex::Primal |
yes |
yes |
not available |
2 |
IloCplex::Dual |
yes |
yes |
not available |
3 |
IloCplex::Network |
yes |
not available |
not available |
4 |
IloCplex::Barrier |
yes |
yes |
yes |
5 |
IloCplex::Sifting |
yes |
not available |
not available |