Incorrect result of MIP solving
AnsweredHi,
For the linked problem (https://gist.github.com/zxt5/d34dd713f8de1e09419ff17a0da75952#file-seed-lp ), I think the correct solution should be 21.65, gurobi returns an incorrect solution (34.88) with the following options:
$> gurobi_cl FeasibilityTol=1e-09 Presolve=2 BarHomogeneous=1 ConcurrentMIP=7 NodeMethod=2 CutAggPasses=102312479 FlowCoverCuts=2 FlowPathCuts=0 GomoryPasses=85007762 seed.lp
Set parameter Username
Set parameter LicenseID to value 2648392
Set parameter FeasibilityTol to value 1e-09
Set parameter BarHomogeneous to value 1
Set parameter NodeMethod to value 2
Set parameter CutAggPasses to value 102312479
Set parameter FlowCoverCuts to value 2
Set parameter FlowPathCuts to value 0
Set parameter GomoryPasses to value 85007762
Set parameter ConcurrentMIP to value 7
Set parameter LogFile to value "gurobi.log"
Set parameter Presolve to value 2
Using license file /home/x27zhou/gurobi.lic
Academic license - for non-commercial use only - expires 2026-04-07
Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (linux64 - "Ubuntu 20.04.5 LTS")
Copyright (c) 2025, Gurobi Optimization, LLC
Read LP format model from file seed.lp
Reading time = 0.00 seconds
OBJ: 210 rows, 14 columns, 2940 nonzeros
Using Gurobi shared library /home/x27zhou/gurobi/gurobi1201/linux64/lib/libgurobi.so.12.0.1
CPU model: AMD Ryzen 9 7950X 16-Core Processor, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 32 threads
Non-default parameters:
FeasibilityTol 1e-09
BarHomogeneous 1
NodeMethod 2
CutAggPasses 102312479
FlowCoverCuts 2
FlowPathCuts 0
GomoryPasses 85007762
ConcurrentMIP 7
Presolve 2
Optimize a model with 210 rows, 14 columns and 2940 nonzeros
Model fingerprint: 0x69ab0908
Variable types: 7 continuous, 7 integer (0 binary)
Coefficient statistics:
Matrix range [1e-02, 1e+02]
Objective range [3e+00, 9e+01]
Bounds range [2e+02, 2e+02]
RHS range [3e+01, 5e+03]
Concurrent MIP optimizer: 7 concurrent instances (2 threads per instance)
Presolve time: 0.00s
Presolved: 210 rows, 14 columns, 2940 nonzeros
Variable types: 7 continuous, 7 integer (0 binary)
Root relaxation presolved: 210 rows, 14 columns, 2940 nonzeros
Root relaxation: objective 5.390218e-01, 40 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - - - - 0.53902 - - 0s
0 0 - - - - 2.46196 - - 0s
0 0 - - - - 2.93215 - - 0s
0 0 - - - - 3.02311 - - 0s
0 0 - - - - 3.11764 - - 0s
0 0 - - - - 3.31960 - - 0s
0 0 - - - - 3.33752 - - 0s
0 0 - - - - 3.34624 - - 0s
0 0 - - - - 3.36774 - - 0s
0 0 - - - - 3.37084 - - 0s
0 0 - - - - 3.38436 - - 1s
0 0 - - - 47.20995 3.40389 92.8% - 1s
0 0 - - - 47.20995 3.50364 92.6% - 1s
0 0 - - - 47.20995 3.50527 92.6% - 1s
0 0 - - - 47.20995 3.52508 92.5% - 1s
0 0 - - - 47.20995 3.52598 92.5% - 1s
0 0 - - - 47.20995 3.52993 92.5% - 1s
0 0 - - - 47.20995 3.53056 92.5% - 1s
0 0 - - - 47.20995 3.55133 92.5% - 1s
0 0 - - - 34.88023 3.56432 89.8% - 1s
0 0 - - - 34.88023 3.58177 89.7% - 1s
0 0 - - - 34.88023 3.59019 89.7% - 1s
0 0 - - - 34.88023 3.61636 89.6% - 1s
0 0 - - - 34.88023 3.62295 89.6% - 1s
0 0 - - - 34.88023 3.62423 89.6% - 1s
0 0 - - - 34.88023 3.66615 89.5% - 2s
0 0 - - - 34.88023 3.67795 89.5% - 2s
0 0 - - - 34.88023 3.69402 89.4% - 2s
0 0 - - - 34.88023 3.72162 89.3% - 2s
0 0 - - - 34.88023 3.72560 89.3% - 2s
0 0 - - - 34.88023 3.72756 89.3% - 2s
0 0 - - - 34.88023 3.77427 89.2% - 2s
0 0 - - - 34.88023 3.77594 89.2% - 2s
0 0 - - - 34.88023 3.77757 89.2% - 2s
0 0 - - - 34.88023 3.78013 89.2% - 2s
0 0 - - - 34.88023 3.79111 89.1% - 2s
0 0 - - - 34.88023 3.79973 89.1% - 2s
0 0 - - - 34.88023 3.80818 89.1% - 2s
Cutting planes:
Gomory: 4
Instance 1 was solved
Explored 1 nodes (249 simplex iterations) in 3.03 seconds (5.01 work units)
Thread count was 2 (of 32 available processors)
Solution count 7: 34.8802 34.8802 47.21 ... 244.487
Optimal solution found (tolerance 1.00e-04)
Best objective 3.488023459579e+01, best bound 3.488023459579e+01, gap 0.0000%
-
Hi Xintong,
I am consistently getting a result of 21.658 on my machine with v12.0.1 using your parameters.
If you vary the value of the Seed parameter do you see different results?
Looking at your parameter settings I am not confident there is good justification for these values. I would stick to the default parameters, it may solve the issue you are experiencing.
- Riley
0 -
Hi,
I have tried several different seed values, the outputs change a little but the results are not changing (still 34.88).
$> gurobi_cl Seed=9832 FeasibilityTol=1e-09 Presolve=2 BarHomogeneous=1 ConcurrentMIP=7 NodeMethod=2 CutAggPasses=102312479 FlowCoverCuts=2 FlowPathCuts=0 GomoryPa
sses=85007762 seed.lp
Set parameter Username
Set parameter LicenseID to value 2648392
Set parameter FeasibilityTol to value 1e-09
Set parameter BarHomogeneous to value 1
Set parameter NodeMethod to value 2
Set parameter CutAggPasses to value 102312479
Set parameter FlowCoverCuts to value 2
Set parameter FlowPathCuts to value 0
Set parameter GomoryPasses to value 85007762
Set parameter ConcurrentMIP to value 7
Set parameter LogFile to value "gurobi.log"
Set parameter Presolve to value 2
Set parameter Seed to value 9832
Using license file /home/x27zhou/gurobi.lic
Academic license - for non-commercial use only - expires 2026-04-07
Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (linux64 - "Ubuntu 20.04.5 LTS")
Copyright (c) 2025, Gurobi Optimization, LLC
Read LP format model from file seed.lp
Reading time = 0.00 seconds
OBJ: 210 rows, 14 columns, 2940 nonzeros
Using Gurobi shared library /home/x27zhou/gurobi/gurobi1201/linux64/lib/libgurobi.so.12.0.1
CPU model: AMD Ryzen 9 7950X 16-Core Processor, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 32 threads
Non-default parameters:
FeasibilityTol 1e-09
BarHomogeneous 1
NodeMethod 2
CutAggPasses 102312479
FlowCoverCuts 2
FlowPathCuts 0
GomoryPasses 85007762
ConcurrentMIP 7
Presolve 2
Seed 9832
Optimize a model with 210 rows, 14 columns and 2940 nonzeros
Model fingerprint: 0x69ab0908
Variable types: 7 continuous, 7 integer (0 binary)
Coefficient statistics:
Matrix range [1e-02, 1e+02]
Objective range [3e+00, 9e+01]
Bounds range [2e+02, 2e+02]
RHS range [3e+01, 5e+03]
Concurrent MIP optimizer: 7 concurrent instances (2 threads per instance)
Presolve time: 0.00s
Presolved: 210 rows, 14 columns, 2940 nonzeros
Variable types: 7 continuous, 7 integer (0 binary)
Root relaxation presolved: 210 rows, 14 columns, 2940 nonzeros
Root relaxation: objective 5.390218e-01, 40 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - - - - 0.53902 - - 0s
0 0 - - - - 2.46196 - - 0s
0 0 - - - - 2.93215 - - 0s
0 0 - - - - 3.02311 - - 0s
0 0 - - - - 3.11764 - - 0s
0 0 - - - - 3.31960 - - 0s
0 0 - - - - 3.33752 - - 0s
0 0 - - - - 3.34624 - - 0s
0 0 - - - - 3.36774 - - 0s
0 0 - - - - 3.37084 - - 0s
0 0 - - - - 3.38436 - - 1s
0 0 - - - 47.20995 3.40389 92.8% - 1s
0 0 - - - 47.20995 3.50364 92.6% - 1s
0 0 - - - 47.20995 3.50527 92.6% - 1s
0 0 - - - 47.20995 3.52508 92.5% - 1s
0 0 - - - 47.20995 3.52598 92.5% - 1s
0 0 - - - 47.20995 3.52993 92.5% - 1s
0 0 - - - 47.20995 3.53056 92.5% - 1s
0 0 - - - 47.20995 3.55133 92.5% - 1s
0 0 - - - 34.88023 3.56432 89.8% - 1s
0 0 - - - 34.88023 3.58177 89.7% - 1s
0 0 - - - 34.88023 3.59019 89.7% - 1s
0 0 - - - 34.88023 3.61636 89.6% - 1s
0 0 - - - 34.88023 3.62295 89.6% - 1s
0 0 - - - 34.88023 3.62423 89.6% - 2s
0 0 - - - 34.88023 3.66615 89.5% - 2s
0 0 - - - 34.88023 3.67795 89.5% - 2s
0 0 - - - 34.88023 3.69402 89.4% - 2s
0 0 - - - 34.88023 3.72162 89.3% - 2s
0 0 - - - 34.88023 3.72560 89.3% - 2s
0 0 - - - 34.88023 3.72756 89.3% - 2s
0 0 - - - 34.88023 3.77427 89.2% - 2s
0 0 - - - 34.88023 3.77594 89.2% - 2s
0 0 - - - 34.88023 3.77757 89.2% - 2s
0 0 - - - 34.88023 3.78013 89.2% - 2s
Cutting planes:
Gomory: 3
Instance 2 was solved
Explored 1 nodes (249 simplex iterations) in 2.96 seconds (5.01 work units)
Thread count was 2 (of 32 available processors)
Solution count 8: 34.8802 34.8802 47.21 ... 253.017
Optimal solution found (tolerance 1.00e-04)
Best objective 3.488023459579e+01, best bound 3.488023459579e+01, gap 0.0000%0 -
How does it go with default values for all parameters?
0 -
The answer is correct with default options. I am just curious about this strange result.
0 -
I just found that changing seed values sometimes changes the result. e.g. seed=9832. wrong; seed=9832243. correct
0 -
Hi Xintong,
I would recommend reading a chapter in our Guidelines for Numerical Issues called "Tolerances and User-Scaling". You will learn about tolerances, models on the edge of infeasibility and the limits of floating point arithmetic.
My guess is that by tightening the feasibilty tolerance to 1e-9 sometimes the optimal solution is being declared infeasible, sometimes it's not, and this depends on the solution path.
Note that later in the the numerical guidelines section we suggest parameters to turn off, or turn down, to help manage numerical issues. These include Presolve, GomoryPasses and Cuts. You can expect by increasing the value of these parameters, as you are doing, you are more likely to cause numerical issues (and therefore incorrect results).
I'll re-iterate that these parameter settings don't make sense to me. Choosing parameter settings should be backed by robust experimental evidence, see How can I make accurate comparisons?, and with an understanding of what the parameter is doing to algorithms in the solver.
- Riley
0 -
I see. Thanks for your detailed answer!
0
Please sign in to leave a comment.
Comments
7 comments