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:

Using license file /opt/gurobi950/gurobi.lic
Read MPS format model from file pilotnov.mps.bz2
Reading time = 0.01 seconds
PILOTNOV: 975 rows, 2172 columns, 13057 nonzeros
Gurobi Optimizer version 9.5.0 build v9.5.0rc0 (linux64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0xe6e7cf84
Coefficient statistics:
  Matrix range     [1e-06, 1e+07]
  Objective range  [2e-03, 1e+00]
  Bounds range     [5e-06, 8e+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, 11455 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -3.2008682e+05   1.274630e+05   0.000000e+00      0s
Extra simplex iterations after uncrush: 1
    1085   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1085 iterations and 0.05 seconds
Optimal objective -4.497276188e+03
Kappa: 1.841766e+07

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

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

Using license file /opt/gurobi950/gurobi.lic
Read MPS format model from file pilotnov.mps.bz2
Reading time = 0.01 seconds
PILOTNOV: 975 rows, 2172 columns, 13057 nonzeros
Gurobi Optimizer version 9.5.0 build v9.5.0rc0 (linux64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0x79ed9354
Coefficient statistics:
  Matrix range     [6e-09, 1e+10]
  Objective range  [5e-06, 9e+02]
  Bounds range     [5e-09, 5e+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.2390277e+32   7.095340e+31   6.239028e+02      0s
Extra simplex iterations after uncrush: 2
    1141   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1141 iterations and 0.05 seconds
Optimal objective -4.497276188e+03
Kappa: 1.166265e+18

This time, the optimization process takes 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:

Using license file /opt/gurobi950/gurobi.lic
Read MPS format model from file pilotnov.mps.bz2
Reading time = 0.01 seconds
PILOTNOV: 975 rows, 2172 columns, 13057 nonzeros
Gurobi Optimizer version 9.5.0 build v9.5.0rc0 (linux64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0xf2c9bd15
Coefficient statistics:
  Matrix range     [9e-12, 1e+13]
  Objective range  [2e-09, 1e+06]
  Bounds range     [6e-12, 4e+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 101 rows and 255 columns
Presolve time: 0.00s
Presolved: 874 rows, 1917 columns, 11897 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -6.8659608e+34   7.041252e+31   6.865961e+04      0s
Extra simplex iterations after uncrush: 47
    1537   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1537 iterations and 0.07 seconds
Optimal objective -4.497276188e+03
Kappa: 1.851538e+25

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 = 5.65274e-05 and residual = 5.65274e-05,


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:

Using license file /opt/gurobi950/gurobi.lic
Read MPS format model from file pilotnov.mps.bz2
Reading time = 0.01 seconds
PILOTNOV: 975 rows, 2172 columns, 13057 nonzeros
Gurobi Optimizer version 9.5.0 build v9.5.0rc0 (linux64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0xfea2a63e
Coefficient statistics:
  Matrix range     [3e-13, 1e+15]
  Objective range  [6e-11, 2e+08]
  Bounds range     [6e-14, 5e+12]
  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 258 columns
Presolve time: 0.00s
Presolved: 872 rows, 1914 columns, 11795 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -9.3067584e+36   7.106821e+31   9.306758e+06      0s

Solved in 1469 iterations and 0.06 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.