Preprocessing: presolver and aggregator

Describes preprocessing in the MIP optimizer.

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 , CPLEX by default automatically preprocesses your problem. Table 1 summarizes the preprocessing parameters. In preprocessing, 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.

Table 1. Parameters to control MIP preprocessing
Interactive Command	Concert Technology Parameter	Callable Library Parameter	Comment	Parameter Reference
set preprocessing aggregator	`AggInd`	`CPX_PARAM_AGGIND`	on by default	preprocessing aggregator application limit
set preprocessing presolve	`PreInd`	`CPX_PARAM_PREIND`	on by default	presolve switch
set preprocessing boundstrength	`BndStrenInd`	`CPX_PARAM_BNDSTRENIND`	presolve must be on	bound strengthening switch
set preprocessing coeffreduce	`CoeRedInd`	`CPX_PARAM_COEREDIND`	presolve must be on	coefficient reduction setting
set preprocessing relax	`RelaxPreInd`	`CPX_PARAM_RELAXPREIND`	applies to relaxation	relaxed LP presolve switch
set preprocessing reduce	`Reduce`	`CPX_PARAM_REDUCE`	all on by default	primal and dual reduction type
set preprocessing numpass	`PrePass`	`CPX_PARAM_PREPASS`	automatic by default	limit on the number of presolve passes made
set preprocessing repeat	`RepeatPresolve`	`CPX_PARAM_REPEATPRESOLVE`	automatic by default	MIP repeat presolve switch

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, 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.

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 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 MIP repeat presolve switch (RepeatPresolve, CPX_PARAM_REPEATPRESOLVE) parameter to invoke this additional step. Its default value of -1 means that 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 2 summarizes the possible values of this parameter.

Table 2. Values of RepeatPresolve 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

CPLEX preprocesses a MIP by default. However, if you use a basis to start LP optimization of the root relaxation, 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.