1
$\begingroup$

I'm solving a large network flow problem using Gurobi to do Benders decomposition in Python. The imported .csvs contain values that typically fall in either zero, the range of [20,200], or with a magnitude of approximately 10^9. I received a warning that the matrix coefficients and RHS were too large, so I scaled down all values that represented quantities by 10^9 and others by 10^3. This solved my coefficient error but not my right-hand side error. Please note that due to some other errors, my model is not completing all its iterations. Here's my log before scaling:

Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 1116052 rows, 575004 columns and 1984260 nonzeros
Model fingerprint: 0x223d0add
Variable types: 355740 continuous, 219264 integer (1024 binary)
Coefficient statistics:
  Matrix range     [8e-02, 2e+10]
  Objective range  [2e-13, 2e-06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e-01, 2e+10]
Warning: Model contains large matrix coefficients
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Found heuristic solution: objective 143424.26885
Presolve removed 1116022 rows and 574935 columns
Presolve time: 1.34s
Presolved: 30 rows, 69 columns, 120 nonzeros
Found heuristic solution: objective 135423.71070
Variable types: 57 continuous, 12 integer (0 binary)

Explored 0 nodes (0 simplex iterations) in 1.75 seconds (1.28 work units)
Thread count was 8 (of 8 available processors)

Solution count 2: 135424 143424 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.354237107007e+05, best bound 1.354237107007e+05, gap 0.0000%

Here's my log after scaling:

Set parameter Username
Academic license - for non-commercial use only - expires 2022-04-25
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 1116052 rows, 575004 columns and 1983740 nonzeros
Model fingerprint: 0x7eba86b8
Variable types: 355740 continuous, 219264 integer (1024 binary)
Coefficient statistics:
  Matrix range     [1e-02, 2e+01]
  Objective range  [2e-13, 2e-06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e-07, 2e+09]
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Found heuristic solution: objective 0.0001434
Presolve removed 1116052 rows and 575004 columns
Presolve time: 1.09s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 1.54 seconds (1.04 work units)
Thread count was 1 (of 8 available processors)

Solution count 2: 0.000143426 0.000143426 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.434261369143e-04, best bound 1.434261369143e-04, gap 0.0000%et parameter Username
Academic license - for non-commercial use only - expires 2022-04-25
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 1116052 rows, 575004 columns and 1983740 nonzeros
Model fingerprint: 0x7eba86b8
Variable types: 355740 continuous, 219264 integer (1024 binary)
Coefficient statistics:
  Matrix range     [1e-02, 2e+01]
  Objective range  [2e-13, 2e-06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e-07, 2e+09]
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Found heuristic solution: objective 0.0001434
Presolve removed 1116052 rows and 575004 columns
Presolve time: 1.09s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 1.54 seconds (1.04 work units)
Thread count was 1 (of 8 available processors)

Solution count 2: 0.000143426 0.000143426 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.434261369143e-04, best bound 1.434261369143e-04, gap 0.0000%
$\endgroup$
6
  • 1
    $\begingroup$ You're RHS has become worse after scaling (with the range of 3e-07 to 2e+09). So, you need to do better scaling there. Also, as gurobi suggested in the log, you can "Consider reformulating model or setting NumericFocus parameter to avoid numerical issues." $\endgroup$
    – EhsanK
    Commented Mar 10, 2022 at 19:01
  • $\begingroup$ @EhsanK I did more rescaling and got these bounds and didn't recieve the warning. In general, if there is no warning should I anticipate any problems? Coefficient statistics: Matrix range [8e-02, 2e+04] Objective range [2e-04, 1e+03] Bounds range [1e+00, 1e+00] RHS range [1e-04, 2e+04] $\endgroup$ Commented Mar 10, 2022 at 19:43
  • 1
    $\begingroup$ Gurobi has a few good links that talk about the ratio of the coefficients. A rough estimate is, the ratio of the largest to the smallest coefficient should be less than 10^9 (but smaller the better). Here are two links that you can read about this further: here and here. $\endgroup$
    – EhsanK
    Commented Mar 10, 2022 at 19:52
  • $\begingroup$ Does your formulation use "big M" constraints? $\endgroup$
    – prubin
    Commented Mar 10, 2022 at 21:25
  • $\begingroup$ @prubin Yes, I am using Big M. M is currently set at 12, but in general it's multiplied by binary variables and set to be greater than some small sums of other binaries. $\endgroup$ Commented Mar 10, 2022 at 22:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.