Unsatisfactory optimization of subproblems

Describes ways to overcome unsatisfactory optimization of difficult subproblems.

In some problems, you can improve performance by evaluating how the continuous LP or QP subproblems are solved at the nodes in the search space, and then possibly modifying the choice of algorithm to solve them.

QCP subproblems are solved only by the barrier optimizer. However, MIQCP models are not always solved by a sequence of QCP subproblems. The MIQCP strategy switch (MIQCPStrat, CPX_PARAM_MIQCPSTRAT) allows you to control what kinds of subproblems are solved in a mixed integer quadratically constrained programming model. Consequently, the following suggestions may also help that class of problem as well.

You can control which algorithm CPLEX applies to the root relaxation of your problem separately from your control of which algorithm CPLEX applies to other subproblems. The following sections explain those parameters more fully.

RootAlg parameter and difficult subproblems

The RootAlg algorithm parameter indicates the algorithm for CPLEX to use on the initial subproblem. In a typical MIP, that initial subproblem is usually the linear relaxation of the original MIP. By default, CPLEX starts the initial subproblem with the dual simplex optimizer. You may have information about your problem that suggests that another optimizer could be more efficient. Table 1 summarizes the values available for the RootAlg parameter.

To set the algorithm for initial MIP relaxation parameter:

In the Interactive Optimizer, use the command set mip strategy startalgorithm with the value to indicate the optimizer you want.
In Concert Technology, use the IloCplex method setParam with the parameter RootAlg and the appropriate algorithm enumeration value.
In the Callable Library, use the routine CPXsetinparam with the parameter CPX_PARAM_STARTALG, and the appropriate symbolic constant.

Table 1. Parameter settings for RootAlg and NodeAlg
Concert Technology Enumeration	Callable Library Symbolic Constant	Setting	Calls this Optimizer
`Auto`	`CPX_ALG_AUTO`	0	automatic
`Primal`	`CPX_ALG_PRIMAL`	1	primal simplex
`Dual`	`CPX_ALG_DUAL`	2	dual simplex (default)
`Network`	`CPX_ALG_HYBNETOPT`	3	network simplex
`Barrier`	`CPX_ALG_BARRIER`	4	barrier with crossover
`Sifting`	`CPX_ALG_SIFTING`	5	sifting
`Concurrent`	`CPX_ALG_CONCURRENT`	6	concurrent: allowed at root, but not at nodes

NodeAlg parameter and difficult subproblems

The NodeAlg parameter indicates the algorithm for CPLEX to use on node relaxations other than the root node. By default, CPLEX applies the dual simplex optimizer to subproblems, and unlike the RootAlg parameter it is extremely unusual for this to not be the most desirable choice, but again, you may have information about your problem that tells you another optimizer could be more efficient. The values and symbolic constants are the same for the NodeAlg parameter as for the RootAlg parameter in Table 1.

To set the MIP subproblem algorithm parameter:

In Concert Technology, use the IloCplex method setParam with the parameter NodeAlg and the appropriate algorithm enumeration value.
In the Callable Library, use the routine CPXsetintparam with the parameter CPX_PARAM_SUBALG, and the appropriate symbolic constant.
In the Interactive Optimizer, use the command set mip strategy subalgorithm with the value to indicate the optimizer you want.

Note:

Only simplex and barrier optimizers can solve problems of type QP (quadratic term in the objective function).

Only the barrier optimizer can solve problems of type QCP (quadratic terms among the constraints).

Solution polishing and difficult subproblems

When subproblems are not solved satisfactorily, another option is to solve as few subproblems of the original model as possible by switching to solution polishing as soon as a first feasible solution is found. This strategy is helpful when finding a good integer solution is more important than proving optimality. For more information about this strategy, see Solution polishing in this manual.