13 Optimizers

Overview

In this section we discuss the algorithmic aspects of the optimizers provided in MOSEK, their termination criteria, configuration options and tuning. The major optimizer classes available are interior-point, simplex and mixed-integer, but the structure of a successful optimization process consists of more steps. Follow the links below for more details:

• Presolve. Its aim is to make the actual optimization more efficient and robust by removing redundancies and linear dependencies, performing reductions, substitutions, dualization, scaling, reordering, symmetry detection and other similar transformations, which, ideally, downsize and simplify the problem for the optimizer. “Easy” problems may be completely solved by presolve and the optimizer will not be invoked.

• Optimization. In this step the actual optimization algorithm suitable for the problem at hand (or explicitly selected by the user) is invoked on the presolved problem. The available optimizers are:

  • Interior-point optimizer for linear problems.

  • Primal and dual simplex optimizers for linear problems.

  • Conic optimizer for nonlinear continuous problems (conic and quadratic).

  • Mixed-integer optimizer whenever the problem contains integer variables or disjunctive constraints.

• Postsolve. This step is essentially about undoing the transformations performed in presolve. It is typically very quick but in some cases may involve more costly algorithmic work, namely:

  • If the problem is linear and basic solution is requested, basis identification needs to be performed.

Linear optimizer Selection

A few different optimizers are available for linear problems: The default is an interior-point method, and the alternative is the simplex method (primal or dual). The optimizer can be selected using the parameter iparam.optimizer.

• The Interior-point or the Simplex Optimizer?

  Given a linear optimization problem, which optimizer is the best: the simplex or the interior-point optimizer? It is impossible to provide a general answer to this question. However, the interior-point optimizer behaves more predictably: it tends to use between 20 and 100 iterations, almost independently of problem size, but cannot perform warm-start. On the other hand the simplex method can take advantage of an initial solution, but is less predictable from cold-start. The interior-point optimizer is used by default. The interior-point solve is (by default) followed by basis identification, so in any case the basic solution is returned.

• The Primal or the Dual Simplex Variant?

  MOSEK provides both a primal and a dual simplex optimizer. Predicting which simplex optimizer is faster is impossible and depends much on the problem structure and size. Setting the iparam.optimizer parameter to optimizertype.free_simplex instructs MOSEK to run both variants in parallel and report the solution from the winner (unless one runs on only one thread, in which case dual simplex is used).

• Warm-start

  When solving a sequence of problems with changing data it is usually more obvious which simplex optimizer to use to best exploit the solution from a preceding solve as warm-start data for the following solve. For instance, if only bounds are changed then the preceding solution remains dual feasible so one will try to employ dual simplex.

To summarize, if you want to know which linear optimizer is faster, it may be worthwhile to try all the options.

Further reading

Below is an extended table of content of the sections summarized above:

• 13.1 Presolve
• 13.2 Linear Interior-point optimizer
  • 13.2.1 The homogeneous primal-dual problem
  • 13.2.2 Interior-point Termination Criterion
  • 13.2.3 Adjusting optimality criteria
  • 13.2.4 The Interior-point Log
• 13.3 The Simplex optimizers
  • 13.3.1 Simplex Termination Criterion
  • 13.3.2 Starting From an Existing Solution
  • 13.3.3 Numerical Difficulties in the Simplex Optimizers
  • 13.3.4 The Simplex Log
• 13.4 Conic Interior-point optimizer
  • 13.4.1 The homogeneous primal-dual problem
  • 13.4.2 Interior-point Termination Criterion
  • 13.4.3 Adjusting optimality criteria
  • 13.4.4 The Conic Interior-point Log
• 13.5 The Mixed-Integer optimizer
  • 13.5.1 Branch-and-Bound
  • 13.5.2 Solution quality and termination criteria
  • 13.5.3 The Mixed-Integer Log
  • 13.5.4 Mixed-Integer Nonlinear Optimization
  • 13.5.5 Disjunctive constraints
  • 13.5.6 Randomization
  • 13.5.7 Further performance tweaks
• 13.6 Basis Identification