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/gurobi900/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.0.0 build v9.0.0rc0 (linux64)
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0x67f9a529
Coefficient statistics:
  Matrix range     [1e-06, 1e+07]
  Objective range  [3e-03, 2e+00]
  Bounds range     [5e-06, 9e+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.2008683e+05   1.550962e+05   0.000000e+00      0s
    1002   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1002 iterations and 0.06 seconds
Optimal objective -4.497276188e+03
Kappa: 7.363754e+06

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/gurobi900/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.0.0 build v9.0.0rc0 (linux64)
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0x94586000
Coefficient statistics:
  Matrix range     [6e-09, 8e+09]
  Objective range  [1e-05, 8e+02]
  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.3809076e+32   7.332854e+31   6.380908e+02      0s
Extra 2 simplex iterations after uncrush
    1556   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1556 iterations and 0.11 seconds
Optimal objective -4.497276188e+03
Kappa: 1.581381e+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:

Using license file /opt/gurobi900/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.0.0 build v9.0.0rc0 (linux64)
Optimize a model with 975 rows, 2172 columns and 13057 nonzeros
Model fingerprint: 0x34ce763e
Coefficient statistics:
  Matrix range     [4e-12, 1e+13]
  Objective range  [2e-08, 1e+06]
  Bounds range     [6e-12, 1e+11]
  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   -7.0386115e+34   6.844498e+31   7.038611e+04      0s
Extra 58 simplex iterations after uncrush
    1552   -4.4972762e+03   0.000000e+00   0.000000e+00      0s

Solved in 1552 iterations and 0.10 seconds
Optimal objective -4.497276188e+03
Warning: unscaled primal violation = 5.65274e-05 and residual = 5.65274e-05
Kappa: 2.969003e+24

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/gurobi900/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.0.0 build v9.0.0rc0 (linux64)
Optimize a model with 975 rows, 2172 columns and 13053 nonzeros
Model fingerprint: 0x5138e90c
Coefficient statistics:
  Matrix range     [3e-13, 1e+15]
  Objective range  [3e-11, 2e+08]
  Bounds range     [4e-14, 9e+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 93 rows and 247 columns
Presolve time: 0.00s
Presolved: 882 rows, 1925 columns, 11753 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -1.0060982e+37   7.198909e+31   1.006098e+07      0s

Solved in 128 iterations and 0.01 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.