Preprocessing: Presolver and Aggregator |
INDEX PREVIOUS NEXT |
When you invoke the MIP optimizer, whether through the Interactive Optimizer command mipopt
, through a call to the Concert Technology IloCplex
method solve
, or through the Callable Library routine CPXmipopt
, ILOG CPLEX by default automatically preprocesses your problem. Table 14.10 summarizes the preprocessing parameters. In preprocessing, ILOG CPLEX applies its presolver and aggregator one or more times to reduce the size of the integer program in order to strengthen the initial linear relaxation and to decrease the overall size of the mixed integer program.
These and other parameters also control the behavior of preprocessing of the continuous subproblem (LP, QP, or QCP) solved during a MIP optimization. See Preprocessing for further details about these parameters in that context. The following discussion pertains to these parameters specifically in MIP preprocessing.
While preprocessing, ILOG CPLEX attempts to strengthen bounds on variables. This bound strengthening may take a long time. In such cases, you may want to turn off bound strengthening.
ILOG CPLEX attempts to reduce coefficients of constraints during preprocessing. Coefficient reduction usually strengthens the continuous relaxation and reduces the number of nodes in the branch & cut tree, but not always. Sometimes, it increases the amount of time needed to solve the linear relaxations at each node, possibly enough time to offset the benefit of fewer nodes. Two levels of coefficient reduction are available, so it is worthwhile to experiment with these preprocessing options to see whether they are beneficial to your problem.
The RelaxPreInd
parameter controls whether an additional round of presolve is applied before ILOG CPLEX solves the continuous subproblem at the root relaxation. Often the root relaxation is the single most time-consuming subproblem solved during branch-and-cut. Certain additional presolve reductions are possible when MIP restrictions are not present, and on difficult models this extra step will often pay off in faster root-solve times. Even when there is no appreciable benefit, there is usually no harm either. However, the RelaxPreInd
parameter is available if you want to explore whether skipping the additional presolve step will improve overall solution speed, for example, if you are solving a long sequence of very easy models and need maximum speed on each one.
It is possible to apply preprocessing a second time, after cuts and other analyses have been performed and before branching begins. If your models tend to require a lot of branching, this technique is sometimes useful in further tightening the formulation. Use the RepeatPresolve
parameter (CPX_PARAM_REPEATPRESOLVE
in the Callable Library) to invoke this additional step. Its default value of -1 means that ILOG CPLEX makes the decision internally whether to repeat presolve; 0 (zero) turns off this feature unconditionally, while positive values allow you control over which aspects of the preprocessed model are re-examined during preprocessing and whether additional cuts are then permitted. Table 14.11 summarizes the possible values of this parameter.
Value |
Effect |
---|---|
-1 |
Automatic (default) |
0 |
Turn off repeat presolve |
1 |
Repeat presolve without cuts |
2 |
Repeat presolve with cuts |
3 |
Repeat presolve with cuts and allow new root cuts |
ILOG CPLEX preprocesses a MIP by default. However, if you use a basis to start LP optimization of the root relaxation, ILOG CPLEX will proceed with that starting basis without preprocessing it. Frequently the strategic benefits of MIP presolve outweigh the tactical advantage of using a starting basis for the root node, so use caution when considering the advantages of a starting basis.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |