Unsatisfactory Optimization of Subproblems

ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solving Mixed Integer Programming Problems (MIP) > Troubleshooting MIP Performance Problems > Unsatisfactory Optimization of Subproblems

Unsatisfactory Optimization of Subproblems

INDEX

PREVIOUS NEXT

In some problems, you can improve performance by evaluating how the continous 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 parameter (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 ILOG CPLEX applies to the root relaxation of your problem separately from your control of which algorithm ILOG CPLEX applies to other subproblems. The following sections explain those parameters more fully.

RootAlg Parameter

The RootAlg algorithm parameter indicates the algorithm for ILOG 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, ILOG CPLEX starts the initial subproblem with the dual simplex optimizer. You may have information about your problem that indicates another optimizer could be more efficient. Table 14.15 summarizes the values available for the RootAlg parameter.

To set this 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 CPXsetintparam with the parameter CPX_PARAM_STARTALG, and the appropriate symbolic constant.

Table 14.15 Settings of RootAlg and NodeAlg Parameters

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

The NodeAlg parameter indicates the algorithm for ILOG CPLEX to use on node relaxations other than the root node. By default, ILOG 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 14.15.

To set the NodeAlg 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).

PREVIOUS NEXT