Giving an initial basis to the simplex solver results in different optimal value depending on LPWarmStart set to 1 or 2 and on the value of NumericFocus
回答済みHello,
We have observed incorrect behaviour in the simplex algorithm when solving a LP model with a given initial basis.
To reproduce the results, the model (test.lp) and the basis (test.bas) can be downloaded from this link.
1. When giving an initial basis to the LP solver and setting LPWarmStart to 1 (default), we obtain an optimal objective value equal to 3.200957306e-02. We observe very large reduced costs (in absolute values) for some variables (>1e+10).
Warm-started the model with the basis from test.bas
Set parameter OutputFlag to value 1
Set parameter LPWarmStart to value 1
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.4 LTS")
CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Non-default parameters:
LPWarmStart 1
NumericFocus 3
Optimize a model with 723 rows, 1199 columns and 3457 nonzeros (Min)
Model has 1 linear objective coefficients
Coefficient statistics:
Matrix range [2e-04, 3e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e-01, 4e+02]
RHS range [5e-01, 5e+01]
LP warm-start: use basis
Iteration Objective Primal Inf. Dual Inf. Time
0 3.2006348e-02 2.765099e-01 0.000000e+00 0s
44 3.2009573e-02 0.000000e+00 0.000000e+00 0s
Solved in 44 iterations and 0.01 seconds (0.00 work units)
Optimal objective 3.200957306e-02
2. When giving the same initial basis to the LP solver and setting LPWarmStart to 2, we obtain an optimal objective value equal to 1.640646376e-02. No very large reduced costs observed in this case. Same output is obtained when setting LPWarmStart to 0 (discard warm-start).
Warm-started the model with the basis from test.bas
Set parameter OutputFlag to value 1
Set parameter LPWarmStart to value 2
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.4 LTS")
CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Non-default parameters:
LPWarmStart 2
NumericFocus 3
Optimize a model with 723 rows, 1199 columns and 3457 nonzeros (Min)
Model has 1 linear objective coefficients
Coefficient statistics:
Matrix range [2e-04, 3e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e-01, 4e+02]
RHS range [5e-01, 5e+01]
LP warm-start: use basis
Presolve time: 0.00s
Presolved: 169 rows, 501 columns, 1383 nonzeros
LP warm-start: get start vectors from basis, then crush them
Crossover log...
2 DPushes remaining with DInf 2.2016272e+18 0s
0 DPushes remaining with DInf 8.9830725e+00 0s
12 PPushes remaining with PInf 1.0624202e-02 0s
0 PPushes remaining with PInf 0.0000000e+00 0s
Push phase complete: Pinf 0.0000000e+00, Dinf 8.9830725e+00 0s
Iteration Objective Primal Inf. Dual Inf. Time
17 5.1832645e-01 0.000000e+00 8.983072e+00 0s
Crossover time: 0.00 seconds (0.00 work units)
35 1.6406464e-02 0.000000e+00 0.000000e+00 0s
Solved in 35 iterations and 0.01 seconds (0.00 work units)
Optimal objective 1.640646376e-02Forcing the use of dual simplex algorithm leads to the same result:
Warm-started the model with the basis from test.bas
Set parameter OutputFlag to value 1
Set parameter Method to value 1
Set parameter LPWarmStart to value 2
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.4 LTS")
CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Non-default parameters:
Method 1
LPWarmStart 2
NumericFocus 2
Optimize a model with 723 rows, 1199 columns and 3457 nonzeros (Min)
Model has 1 linear objective coefficients
Coefficient statistics:
Matrix range [2e-04, 3e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e-01, 4e+02]
RHS range [5e-01, 5e+01]
LP warm-start: use basis
Presolve time: 0.00s
Presolved: 169 rows, 501 columns, 1383 nonzeros
LP warm-start: get start vectors from basis, then crush them
Dual warm-start: 108 superbasic variables.
Iteration Objective Primal Inf. Dual Inf. Time
0 -6.6642916e+35 1.901272e+30 6.664292e+05 0s
307 1.6406464e-02 0.000000e+00 0.000000e+00 0s
Solved in 307 iterations and 0.01 seconds (0.01 work units)
Optimal objective 1.640646376e-023. Setting NumericFocus to 1 or 2 in the first case (initial basis and LPWarmStart = 1) leads to the following output :
Warm-started the model with the basis from test.bas
Set parameter OutputFlag to value 1
Set parameter LPWarmStart to value 1
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.4 LTS")
CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Non-default parameters:
LPWarmStart 1
NumericFocus 1
Optimize a model with 723 rows, 1199 columns and 3457 nonzeros (Min)
Model has 1 linear objective coefficients
Coefficient statistics:
Matrix range [2e-04, 3e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e-01, 4e+02]
RHS range [5e-01, 5e+01]
LP warm-start: use basis
Iteration Objective Primal Inf. Dual Inf. Time
0 2.8261822e-02 2.786389e-01 0.000000e+00 0s
55 2.7501655e-02 0.000000e+00 0.000000e+00 0s
Solved in 55 iterations and 0.00 seconds (0.00 work units)
Optimal objective 2.750165465e-02
For more context, the basis was the optimal basis of the same LP but with different bounds on the xh, co2_emission, and rn_generation variables, as well as different coefficients in the constraints for the lambda variable (file test2.lp).
Do you have any thoughts on what is going on here?
Thanks for your time.
Best regards,
Aurélien
-
Hi Aurélien,
The basis provided is extremely ill-conditioned. We can calculate the Kappa value like so:
import gurobipy as gp m = gp.read("test.lp") m.read("test.bas") m.params.IterationLimit=0 m.optimize() print(m.KappaExact)The Kappa value is over 1e15 which is not good. Values up to 1e8 indicate good numerics, above 1e10 is asking for instability, and above 1e14 is asking for disaster.
If you ask Gurobi to start with such a problematic basis then it is not surprising that incorrect conclusions are reached.
The first 30 minutes of this webinar recording will be useful for some background information:
Numerical Issues, Gurobi Days Digital 2022- Riley
0
サインインしてコメントを残してください。
コメント
1件のコメント