13.3 The Simplex optimizers

MOSEK provides a primal and dual simplex algorithm implementation for linear problems.

13.3.1 Simplex Termination Criterion

The simplex optimizer terminates when it finds an optimal basic solution or an infeasibility certificate. A basic solution is optimal when it is primal and dual feasible; see Sec. 12.1 (Linear Optimization) for a definition of the primal and dual problem. Due to the fact that computations are performed in finite precision MOSEK allows violations of primal and dual feasibility within certain tolerances. The user can control the allowed primal and dual tolerances with the parameters MSK_DPAR_BASIS_TOL_X and MSK_DPAR_BASIS_TOL_S.

13.3.2 Starting From an Existing Solution

When using the simplex optimizer it may be possible to reuse an existing solution and thereby reduce the solution time significantly. When a simplex optimizer starts from an existing solution it is said to perform a warm-start. If the user is solving a sequence of optimization problems by solving the problem, making modifications, and solving again, MOSEK will warm-start automatically.

By default MOSEK uses presolve when performing a warm-start. If the optimizer only needs very few iterations to find the optimal solution it may be better to turn off the presolve.

13.3.3 Numerical Difficulties in the Simplex Optimizers

Though MOSEK is designed to minimize numerical instability, completely avoiding it is impossible when working in finite precision. MOSEK treats a “numerically unexpected behavior” event inside the optimizer as a set-back. The user can define how many set-backs the optimizer accepts; if that number is exceeded, the optimization will be attempted in extended floating point precision (increasing numerical stability at the expenses of computational speed) or aborted, depending on settings. Set-backs are a way to escape long sequences where the optimizer tries to recover from an unstable situation.

Examples of set-backs are: repeated singularities when factorizing the basis matrix, repeated loss of feasibility, degeneracy problems (no progress in objective) and other events indicating numerical difficulties. If the simplex optimizer encounters a lot of set-backs the problem is usually badly scaled; in such a situation try to reformulate it into a better scaled problem. Then, if a lot of set-backs still occur, trying one or more of the following suggestions may be worthwhile:

• Raise tolerances for allowed primal or dual feasibility: increase the value of

  • MSK_DPAR_BASIS_TOL_X, and

  • MSK_DPAR_BASIS_TOL_S.

• Raise or lower pivot tolerance: Change the MSK_DPAR_SIMPLEX_ABS_TOL_PIV parameter.

• Switch optimizer: Try another optimizer.

• Switch off crash: Set both MSK_IPAR_SIM_PRIMAL_CRASH and MSK_IPAR_SIM_DUAL_CRASH to 0.

• Experiment with other pricing strategies: Try different values for the parameters

  • MSK_IPAR_SIM_PRIMAL_SELECTION and

  • MSK_IPAR_SIM_DUAL_SELECTION.

• If you are using warm-starts, in rare cases switching off this feature may improve stability. This is controlled by the MSK_IPAR_SIM_HOTSTART parameter.

• Increase maximum number of set-backs allowed controlled by MSK_IPAR_SIM_MAX_NUM_SETBACKS.

• If the problem repeatedly becomes infeasible try switching off the special degeneracy handling. See the parameter MSK_IPAR_SIM_DEGEN for details.

13.3.4 The Simplex Log

Below is a typical log output from the simplex optimizer:

Simplex optimizer started.
Constraints: 667          Variables: 2335         Dualized: No
Using 64 bit floating point precision.
Iter       Ncand      PFEAS        DFEAS        POBJ               DOBJ               STAGE    Time
1          4          NA           3.62e-01     NA                 NA                 D1       0.00
6          327        NA           0.00e+00     NA                 -5.120807e+04      D2       0.00
2733       0          NA           1.11e-10     NA                 5.501846e+03       P3       0.10
Simplex optimizer terminated. Time: 0.10

The first lines summarize the problem the optimizer is solving and various settings. This is followed by the iteration log, with the following meaning:

• Iter: Number of iterations.

• Ncand: Number of pricing candidates.

• PFEAS: Primal feasibility measure reported by the simplex optimizer.

• DFEAS: Dual feasibility measure reported by the simplex optimizer.

• POBJ: An estimate for the primal objective value (when the primal variant is used).

• DOBJ: An estimate for the dual objective value (when the dual variant is used).

• STAGE: A combination of: simplex optimizer: (P) primal | (D) dual ; simplex phase: (0) initialization | (1) seek feasibility | (2) seek optimality | (3) seek purification.

• Time: Time spent since this instance of the simplex optimizer was invoked (in seconds).