Preprocessing
Documents preprocessing at default parameter settings in LP optimizers.
At default settings, CPLEX preprocesses problems by simplifying constraints, reducing problem size, and eliminating redundancy. Its presolver tries to reduce the size of a problem by making inferences about the nature of any optimal solution to the problem. Its aggregator tries to eliminate variables and rows through substitution. For most models, preprocessing is beneficial to the total solution speed, and CPLEX reports the model's solution in terms of the user's original formulation, making the exact nature of any reductions immaterial.
Dual formulation in presolve
A useful preprocessing feature for performance tuning, one that is not always activated by default, can be to convert the problem to its dual formulation. The nature of the dual formulation is rooted in linear programming theory, beyond the scope of this manual, but for the purposes of this preprocessing feature it is sufficient to think of the roles of the rows and columns of the model's constraint matrix as being switched. Thus the feature is especially applicable to models that have many more rows than columns.
You can direct the preprocessor to form the dual by setting
the PreDual parameter to 1 (one).
Conversely, to entirely inhibit the dual formulation
for the barrier optimizer, you can set the PreDual parameter
to -1 . The default, automatic, setting
is 0 .
It is worth emphasizing, to those familiar with linear
programming theory, that the decision to solve the dual formulation
of your model, via this preprocessing parameter, is not the same as
the choice between using the dual simplex method or the primal simplex
method to perform the optimization. Although these two concepts (dual
formulation and dual simplex optimizer) have theoretical foundations
in common, it is valid to consider, for example, solving the dual
formulation of your model with the dual simplex method; this would
not simply result in the same computational path as solving the primal
formulation with the primal simplex method. However, with that distinction
as background, it may be worth knowing that when CPLEX generates the
dual formulation, and a simplex optimizer is to be used, CPLEX will
in most cases automatically select the opposite simplex optimizer
to the one it would have selected for the primal formulation. Thus,
if you set the PreDual parameter to 1 (one),
and also select LPMethod 1 (which normally
invokes the primal simplex optimizer), the dual simplex optimizer
will be used in solving the dual formulation. Because solution status
and the other results of an optimization are the same regardless of
these settings, no additional steps need to be taken by the user to
use and interpret the solution; but examination of solution logs might
prove confusing if this behavior is not taken into account.
Dependency checking in presolve
| Setting | Effect |
|---|---|
| -1 | automatic: let CPLEX choose when to use dependency checking |
| 0 | turn off dependency checking (default) |
| 1 | turn on only at the beginning of preprocessing |
| 2 | turn on only at the end of preprocessing |
| 3 | turn on at beginning and at end of preprocessing |
Final factor after presolve
When presolve makes changes to the model prior to optimization,
a reverse operation (uncrush) occurs at termination to restore the
full model with its solution. With default settings, the simplex optimizers
will perform a final basis factorization on the full model before
terminating. If you turn on the memory emphasis parameter (memory reduction switch: MemoryEmphasis
(bool), CPX_PARAM_MEMORYEMPHASIS (int))
to conserve memory, the final factorization after uncrushing will
be skipped; on large models this can save some time, but computations
that require a factorized basis after optimization (for example the
computation of the condition number Kappa) may be unavailable depending
on the operations presolve performed.
Factorization can easily be performed later by a call
to a simplex optimizer with the parameter AdvInd set
to a value greater than or equal to one.
Memory use and presolve
To reduce memory use, presolve may compress the arrays
used for storage of the original model. This compression can make
more memory available for the optimizer that the user has called.
To conserve memory, you can also turn on the memory emphasis parameter
(memory reduction switch: MemoryEmphasis
(bool), CPX_PARAM_MEMORYEMPHASIS (int))
.
Controlling passes in preprocessing
In rare instances, a user may wish to specify the number
of analysis passes that the presolver or the aggregator makes through
the problem. The parameters PrePass and AggInd ,
respectively, control these two preprocessing features; the default, automatic ,
setting of -1 lets CPLEX decide the number
of passes to make, while a setting of 0 directs
CPLEX not to use that preprocessing feature, and a positive integer
limits the number of passes to that value. At the automatic setting,
CPLEX applies the aggregator just once when it is solving the LP model;
for some problems, it may be worthwhile to increase the AggInd setting.
The behavior under the PrePass default
is less easy to predict, but if the output log indicates it is performing
excessive analysis, you may wish to try a limit of five passes or
some other modest value.
Aggregator fill in preprocessing
Another parameter, which affects only the aggregator,
is AggFill. Occasionally the substitutions
made by the aggregator will increase matrix density and thus make
each iteration too expensive to be advantageous. In such cases, try
lowering AggFill from its default value
of 10. CPLEX may make fewer substitutions
as a consequence, and the resulting problem will be less dense.
Turning off preprocessing
Finally, if for some reason you wish to turn CPLEX preprocessing
entirely off, set the parameter PreInd to
0 (zero).