Scaling jeopardizes Simplex convergence

回答済み

Manuel Bröchin

2021年02月08日 14:43

• 
• 
• 

Hi,

We're solving energy system models (often LPs without integrality constraints) and we're trying to improve the numerical properties of these models by scaling the input values.

The scaling approach so far tries to minimize the numeric range of values in the model while: (1) avoiding rounding of input by choosing scaling factors as powers of 2, (2) avoiding scaling any values below the Gurobi tolerances of 10^-6

We solve these models using barrier with crossover. Despite scaling the models we experience numerical issues in the simplex phase of crossover. Concretely we observe the following pattern:

Simplex takes primal (or dual) steps until at some point it doesn’t seem to make any more progress on the objective, then Simplex ”takes a leap” (giving up feasibility for optimality or vice versa) and continues doing dual (or primal) steps. This is exemplified by the following extract from the simplex phase of a Gurobi log:

Iteration   |   Objective      |   Primal Inf.    |   Dual Inf.
------------+------------------+------------------+----------------
   1652163  |   9.9067687e+04  |   0.000000e+00   |   3.592856e+00
   1652493  |   9.9067687e+04  |   0.000000e+00   |   1.540992e+00
   1652913  |   9.9067687e+04  |   0.000000e+00   |   7.386038e-01
   1653274  |   9.9067687e+04  |   0.000000e+00   |   8.657328e-02
   1653588  |   9.9069384e+04  |   4.680475e+03   |   0.000000e+00
   1654008  |   9.9069385e+04  |   2.144838e+04   |   0.000000e+00

This pattern often repeats until the time limit is reached but there are other cases where simplex eventually converges to a solution.

The crucial part is: while scaling often reduces average time to solve a specific model (averaged over e.g. 10 runs, only changing the random seed of Gurobi), it also makes extremely long runtimes more likely. In all runs with extremely long runtimes we observe the above pattern.

For example, the following are the runtimes of 10 runs of a scaled and an unscaled version of the same model:

scaled: 
4936.1, 4976.9, 5236.6, 5356.7, 5795.8, 6153.7, 6936.3, 22286.1, 67368.1, 80566.9
unscaled: 
11247.3, 11283.6, 12235.8, 12853.9, 14356.9, 14396.5, 14694.2, 14776.6, 14852.0, 28613.9

Even though median runtime is much lower in the scaled model, 2 out of 10 runs have extremely long runtimes.

I have two questions:

1.  Is the objective for scaling as described above sensible? Our main goal is to improve numerical stability to avoid non-convergence but somehow our scaling seems to adversely affect numerical stability
2. Does the simplex behavior of jumping between primal and dual feasible points (as seen in the log) indicate a concrete numerical issue we could address by modifying our scaling strategy?

Thank you very much in advance!

Kind regards,

Manuel Bröchin

 

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 03:00 編集済み

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  2021年02月12日 08:42

  Hi Manuel,

   Is the objective for scaling as described above sensible? Our main goal is to improve numerical stability to avoid non-convergence but somehow our scaling seems to adversely affect numerical stability

  In general, scaling helps to avoid numerical issues and as you can see it actually halves the runtime (for 8 out of 10 runs). However, even a well-scaled model may suffer from numerical issues. The coefficient ranges are just an indicator and do not guarantee numerical stability in any way.

  Does the simplex behavior of jumping between primal and dual feasible points (as seen in the log) indicate a concrete numerical issue we could address by modifying our scaling strategy?

  The stability and convergence in the scaled case are very likely affected by an ill-conditioning of the coefficient matrix. Note that the coefficient matrix can be ill-conditioned even for acceptable coefficient ranges. You could try experimenting with the NumericFocus parameter to avoid this behavior. The work by Ed Klotz on ill-conditioning and numerical instability may be a good guide to narrow down the problem.

  Best regards,
  Jaromił

   

  0

投稿コメントは受け付けていません。