13.3 The Simplex optimizers

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

13.3.1 The free simplex optimizer

In general for a given optimization problem it is hard to know whether the primal or dual simplex optimizer will solve the problem fastest. Therefore, an optimizer called the simplex is available that will apply the primal and dual optimizers concurrently to the problem. This assumes that two or more threads are available.

In other words a horse race between is performed. In general such a race will not be deterministic due the operating systems handling of threads are not deterministic. However, given the free simplexis terminated early due for instance a time limit, then it will be run-to-run deterministic i.e. the same solution wil be returned for exactly the same input. This is achived using a deterministic time measure which tends to be corrolated with wall clock time. The idea is when the first optimizer terminates then the other optimizers are first terminated when they have used at least same amount of as first optimizer. Finally, among the optimizers that have solved the problem a deterministic tie-breaking strategy is to choose the winning optimizer.

Below is an example log output from running the free simplex on a problem.

Concurrent optimizer started.
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.13
Simplex optimizer terminated. Time: 0.13
Concurrent optimizer mode: deterministic
Concurrent optimizer summary
  Optimizer             Time(s)   Ticks(G)              Ticks(G)/Time(s)      Winner
  dual simplex          0.14      6                     3.9e+01
  primal simplex        0.14      5                     3.3e+01               yes
Concurrent optimizer terminated. Time: 0.14
Optimizer terminated. Time: 0.14

Open file 'out\jobs\runmosek\stat\brylle\default-25fv47.stat'

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 5.5018458883e+03    nrm: 5e+03    Viol.  con: 9e-13    var: 3e-14
  Dual.    obj: 5.5018458883e+03    nrm: 1e+02    Viol.  con: 0e+00    var: 4e-08

The log shows that the concurrent optimizers has run the primal and dual simplex optimizers concurrently. Moreover, it can be seen that the concurrent optimizer employed the deterministic mode and the primal simplex is the winner for this problem.

13.3.2 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 Dparam::BASIS_TOL_X and Dparam::BASIS_TOL_S.

13.3.3 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.4 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

  • Dparam::BASIS_TOL_X, and

  • Dparam::BASIS_TOL_S.

• Raise or lower pivot tolerance: Change the Dparam::SIMPLEX_ABS_TOL_PIV parameter.

• Switch optimizer: Try another optimizer.

• Switch off crash: Set both Iparam::SIM_PRIMAL_CRASH and Iparam::SIM_DUAL_CRASH to 0.

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

  • Iparam::SIM_PRIMAL_SELECTION and

  • Iparam::SIM_DUAL_SELECTION.

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

• Increase maximum number of set-backs allowed controlled by Iparam::SIM_MAX_NUM_SETBACKS.

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

13.3.5 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).