Documentation

Why scaling and geometry is relevant

This section provides a simple example of how scaling problems can slow down problem solving and, in extreme cases, result in unexpected answers. Consider the problem:

and let be a diagonal matrix where . In theory, solving should be equivalent to solving the related problem :

However, in practice, the two models behave very differently. To demonstrate this, we use a simple script rescale.py that randomly rescales the columns of the model. Let's consider the impact of rescaling on the problem pilotnov.mps.bz2. Solving the original problem gives the following output:

Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Coefficient statistics:
  Matrix range     [3e-06, 9e+06]
  Objective range  [3e-03, 1e+00]
  Bounds range     [6e-06, 7e+04]
  RHS range        [1e-05, 4e+04]
Warning: Model contains large matrix coefficient range
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Presolve removed 254 rows and 513 columns
Presolve time: 0.01s
Presolved: 721 rows, 1659 columns, 11454 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -3.2008682e+05   1.435603e+05   0.000000e+00      0s
    1137   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1137 iterations and 0.13 seconds
Optimal objective -4.497276188e+03
Kappa: 1.949838e+06

Note the log message regarding the matrix coefficient range in the log (which in this case shows a range of [3e-06, 9e+06]).

If we run rescale.py -f pilotnov.mps.bz2 -s 1e3 (randomly rescaling columns up or down by as much as ), we obtain:

Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Coefficient statistics:
  Matrix range     [5e-09, 1e+10]
  Objective range  [2e-06, 1e+03]
  Bounds range     [5e-09, 6e+07]
  RHS range        [1e-05, 4e+04]
Warning: Model contains large matrix coefficient range
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Presolve removed 100 rows and 255 columns
Presolve time: 0.00s
Presolved: 875 rows, 1917 columns, 11899 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -6.2117921e+32   7.026405e+31   6.211792e+02      0s
Extra 2 simplex iterations after uncrush
    1166   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1166 iterations and 0.15 seconds
Optimal objective -4.497276188e+03
Kappa: 2.341493e+18

This time, the optimization process takes a more iterations, and also, we get an extra warning:


Extra 2 simplex iterations after uncrush,


This indicates that extra simplex iterations were performed on the unpresolved model. Also, note the very large value for Kappa; its meaning will be discussed in this section.

If we run rescale.py -f pilotnov.mps.bz2 -s 1e6, we obtain:

Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Coefficient statistics:
  Matrix range     [5e-12, 1e+13]
  Objective range  [2e-09, 1e+06]
  Bounds range     [5e-12, 5e+10]
  RHS range        [1e-05, 4e+04]
Warning: Model contains large matrix coefficient range
Warning: Model contains large bounds
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Presolve removed 103 rows and 252 columns
Presolve time: 0.01s
Presolved: 872 rows, 1920 columns, 11900 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -6.4093202e+34   7.254491e+31   6.409320e+04      0s
Extra 151 simplex iterations after uncrush
    1903   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1903 iterations and 0.23 seconds
Optimal objective -4.497276188e+03
Warning: unscaled primal violation = 0.171778 and residual = 0.00142752
Kappa: 5.729068e+12

Now we get a much larger number of extra simplex iterations, and more troublingly, we get a warning about the quality of the resulting solution:


Warning: unscaled primal violation = 0.171778 and residual = 0.00142752,


This message indicates that the solver had trouble finding a solution that satisfies the default tolerances.

Finally, if we run rescale.py -f pilotnov.mps.bz2 -s 1e8, we obtain:

Optimize a model with 975 rows, 2172 columns and 13054 nonzeros
Coefficient statistics:
  Matrix range     [3e-13, 7e+14]
  Objective range  [2e-11, 1e+08]
  Bounds range     [5e-14, 1e+13]
  RHS range        [1e-05, 4e+04]
Warning: Model contains large matrix coefficient range
Warning: Model contains large bounds
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Presolve removed 79 rows and 242 columns
Presolve time: 0.00s

Solved in 0 iterations and 0.00 seconds
Infeasible model

In this case, the optimization run terminates almost instantly, but with the unexpected Infeasible result.

As you can see, as we performed larger and larger rescalings, we continued to obtain the same optimal value, but there were clear signs that the solver struggled. We see warning messages, as well increasing iteration counts, runtimes, and Kappa values. However, once we pass a certain rescaling value, the solver is no longer able to solve the model and instead reports that it is Infeasible.

Note that this is not a bug in Gurobi. It has to do with changing the meaning of numbers depending on their range, the use of fixed tolerances, and in the changing geometry of the problem due to scaling. We will discuss this topic further in a later section.