12.1 Presolve

Before an optimizer actually performs the optimization the problem is preprocessed using the so-called presolve. The purpose of the presolve is to

  1. remove redundant constraints,

  2. eliminate fixed variables,

  3. remove linear dependencies,

  4. substitute out (implied) free variables, and

  5. reduce the size of the optimization problem in general.

After the presolved problem has been optimized the solution is automatically postsolved so that the returned solution is valid for the original problem. Hence, the presolve is completely transparent. For further details about the presolve phase, please see [AA95] and [AGMeszarosX96].

It is possible to fine-tune the behavior of the presolve or to turn it off entirely. If presolve consumes too much time or memory compared to the reduction in problem size gained it may be disabled. This is done by setting the parameter MSK_IPAR_PRESOLVE_USE to "MSK_PRESOLVE_MODE_OFF".

In the following we describe in more detail the presolve applied to continuous, i.e., linear and conic optimization problems, see Sec. 12.2 (Linear Optimization) and Sec. 12.3 (Conic Optimization - Interior-point optimizer). The mixed-integer optimizer, Sec. 12.4 (The Optimizer for Mixed-Integer Problems), applies similar techniques. The two most time-consuming steps of the presolve for continuous optimization problems are

  • the eliminator, and

  • the linear dependency check.

Therefore, in some cases it is worthwhile to disable one or both of these.

Numerical issues in the presolve

During the presolve the problem is reformulated so that it hopefully solves faster. However, in rare cases the presolved problem may be harder to solve then the original problem. The presolve may also be infeasible although the original problem is not. If it is suspected that presolved problem is much harder to solve than the original, we suggest to first turn the eliminator off by setting the parameter MSK_IPAR_PRESOLVE_ELIMINATOR_MAX_NUM_TRIES to 0. If that does not help, then trying to turn entire presolve off may help.

Since all computations are done in finite precision, the presolve employs some tolerances when concluding a variable is fixed or a constraint is redundant. If it happens that MOSEK incorrectly concludes a problem is primal or dual infeasible, then it is worthwhile to try to reduce the parameters MSK_DPAR_PRESOLVE_TOL_X and MSK_DPAR_PRESOLVE_TOL_S. However, if reducing the parameters actually helps then this should be taken as an indication that the problem is badly formulated.

Eliminator

The purpose of the eliminator is to eliminate free and implied free variables from the problem using substitution. For instance, given the constraints

\[\begin{split}\begin{array} {rcl} y & = & \sum_j x_j, \\ y,x & \geq & 0, \end{array}\end{split}\]

y is an implied free variable that can be substituted out of the problem, if deemed worthwhile. If the eliminator consumes too much time or memory compared to the reduction in problem size gained it may be disabled. This can be done by setting the parameter MSK_IPAR_PRESOLVE_ELIMINATOR_MAX_NUM_TRIES to 0. In rare cases the eliminator may cause that the problem becomes much hard to solve.

Linear dependency checker

The purpose of the linear dependency check is to remove linear dependencies among the linear equalities. For instance, the three linear equalities

\[\begin{split}\begin{array} {rcl} x_1 + x_2 + x_3 & = & 1, \\ x_1 + 0.5 x_2 & = & 0.5, \\ 0.5 x_2 + x_3 & = & 0.5. \\ \end{array}\end{split}\]

contain exactly one linear dependency. This implies that one of the constraints can be dropped without changing the set of feasible solutions. Removing linear dependencies is in general a good idea since it reduces the size of the problem. Moreover, the linear dependencies are likely to introduce numerical problems in the optimization phase. It is best practice to build models without linear dependencies, but that is not always easy for the user to control. If the linear dependencies are removed at the modeling stage, the linear dependency check can safely be disabled by setting the parameter MSK_IPAR_PRESOLVE_LINDEP_USE to "MSK_OFF".

Dualizer

All linear, conic, and convex optimization problems have an equivalent dual problem associated with them. MOSEK has built-in heuristics to determine if it is more efficient to solve the primal or dual problem. The form (primal or dual) is displayed in the MOSEK log and available as an information item from the solver. Should the internal heuristics not choose the most efficient form of the problem it may be worthwhile to set the dualizer manually by setting the parameters:

Note that currently only linear and conic (but not semidefinite) problems may be automatically dualized.

Scaling

Problems containing data with large and/or small coefficients, say \(1.0e+9\) or \(1.0e-7\), are often hard to solve. Significant digits may be truncated in calculations with finite precision, which can result in the optimizer relying on inaccurate data. Since computers work in finite precision, extreme coefficients should be avoided. In general, data around the same order of magnitude is preferred, and we will refer to a problem, satisfying this loose property, as being well-scaled. If the problem is not well scaled, MOSEK will try to scale (multiply) constraints and variables by suitable constants. MOSEK solves the scaled problem to improve the numerical properties.

The scaling process is transparent, i.e. the solution to the original problem is reported. It is important to be aware that the optimizer terminates when the termination criterion is met on the scaled problem, therefore significant primal or dual infeasibilities may occur after unscaling for badly scaled problems. The best solution of this issue is to reformulate the problem, making it better scaled.

By default MOSEK heuristically chooses a suitable scaling. The scaling for interior-point and simplex optimizers can be controlled with the parameters MSK_IPAR_INTPNT_SCALING and MSK_IPAR_SIM_SCALING respectively.