Nonzero gap for optimal solution?
Answered
Hi!
For many instances, I get results that Gurobi (9.1.1) says are optimal, but which still have a large gap. For example:
Optimal solution found (tolerance 1.00e-04)
Best objective 1.250000000000e+02, best bound 1.450000000000e+02, gap 16.0000%
I assume this means that it has proved optimality in some other manner than finding a tight bound?
(I see similar questions have been asked before, but could find an answer that applied directly.)
– Magnus
-
Hi Magnus,
Do you set the TimeLimit parameter or any other parameter? Could you provide the first ~30 and the lest ~ 20 lines of the Gurobi LOG?
Best regards,
Jaromił0 -
Yes, I set the TimeLimit parameter, but it is set to 300, and this MIP finishes in 0.02 seconds. (I also set NodefileStart to 1.0.)
Here is the entire log:
Gurobi 9.1.1 (mac64) logging started Wed Feb 24 13:33:50 2021
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 18 rows, 73 columns and 144 nonzeros
Model fingerprint: 0x7ef0eb93
Variable types: 1 continuous, 72 integer (72 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective -0.0000000
Presolve removed 1 rows and 6 columns
Presolve time: 0.00s
Presolved: 17 rows, 67 columns, 138 nonzeros
Variable types: 0 continuous, 67 integer (66 binary)Root relaxation: objective 1.665000e+02, 33 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 166.50000 0 10 -0.00000 166.50000 - - 0s
H 0 0 122.0000000 166.50000 36.5% - 0s
H 0 0 125.0000000 166.50000 33.2% - 0s
0 0 166.00000 0 16 125.00000 166.00000 32.8% - 0s
0 0 166.00000 0 14 125.00000 166.00000 32.8% - 0s
0 0 166.00000 0 16 125.00000 166.00000 32.8% - 0s
0 0 166.00000 0 16 125.00000 166.00000 32.8% - 0s
0 0 165.34487 0 12 125.00000 165.34487 32.3% - 0s
0 0 165.17133 0 20 125.00000 165.17133 32.1% - 0s
0 0 163.67979 0 21 125.00000 163.67979 30.9% - 0s
0 0 163.01932 0 19 125.00000 163.01932 30.4% - 0s
0 0 162.87106 0 20 125.00000 162.87106 30.3% - 0s
0 0 161.52527 0 28 125.00000 161.52527 29.2% - 0s
0 0 157.43258 0 19 125.00000 157.43258 25.9% - 0s
0 0 157.39406 0 20 125.00000 157.39406 25.9% - 0s
0 0 157.30748 0 22 125.00000 157.30748 25.8% - 0s
0 0 157.26790 0 22 125.00000 157.26790 25.8% - 0s
0 0 157.26790 0 23 125.00000 157.26790 25.8% - 0s
0 0 153.30579 0 18 125.00000 153.30579 22.6% - 0s
0 0 145.92841 0 16 125.00000 145.92841 16.7% - 0sCutting planes:
Gomory: 3
Cover: 2
MIR: 10
RLT: 1Explored 1 nodes (457 simplex iterations) in 0.02 seconds
Thread count was 8 (of 8 available processors)Solution count 3: 125 122 -0
Optimal solution found (tolerance 1.00e-04)
Best objective 1.250000000000e+02, best bound 1.450000000000e+02, gap 16.0000%User-callback calls 124, time in user-callback 0.00 sec
0 -
We can see that there were 124 User-callback calls. Do you perform anything specific in the callbacks?
Could you provide an MPS file? You can write an MPS file using the Model.write() function. The Knowledge Base article Posting to the Community Forum explains how to provide model files in the Community.0 -
I have not added any callbacks on purpose, at least; I'm accessing Gurob i through JuMP.jl, and I guess some callbacks may have been set up there.
The solver use is part of code that runs many models, but I've tried to make sure I extracted the right one, using GURO_PAR_DUMP. Here's the resulting MPS file.
0 -
While I'd like to know what's going on, my primary concern is whether the result is, indeed, optimal; I assume there is no reason to suspect otherwise, given that Gurobi explicitly says so?
0 -
It seems to be an output error. Setting NumericFocus=1 or Presolve=2 seems to be a valid workaround. Thank you for reporting this.
1 -
Thank you. I can confirm that the gap of 16% was also reported through the API; in the case of JuMP, when using MOI.get(model, MOI.RelativeGap()), though this should access the Gurobi library directly, and not be related to the logging. I guess you're not just referring to the log when you say “output error”, but I thought I'd clarify, just in case.
Anyway, thanks for your help.
0 -
Also: Would this affect the optimality of the returned result? I.e., do I need to set NumericFocus or Presolve for Gurobi to give me the right answer, here?
1 -
Also: Would this affect the optimality of the returned result? I.e., do I need to set NumericFocus or Presolve for Gurobi to give me the right answer, here?
The result provided by Gurobi is optimal. Thus, in this case, you don't have to set the additional parameters. Just, if you wish to get the 0% gap to be reported in the LOG file and through the API, then you need to set one of the mentioned parameters as a workaround.
1 -
Thanks!
0 -
I see the same behavior on a different model. Here is my log output. I tried setting the parameters Jaromil suggested, but that did not change anything. Please advise as this log results in mistrust in the solution given as the gap is not what is expected.
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (mac64[arm])
CPU model: Apple M2 Max
Thread count: 12 physical cores, 12 logical processors, using up to 12 threadsOptimize a model with 491136 rows, 428692 columns and 1085710 nonzeros
Model fingerprint: 0x70df0439
Variable types: 356968 continuous, 71724 integer (71724 binary)
Coefficient statistics:
Matrix range [6e-09, 1e+04]
Objective range [2e+02, 2e+07]
Bounds range [1e-05, 1e+05]
RHS range [1e+00, 1e+00]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Found heuristic solution: objective -7.47932e+07
Presolve removed 471182 rows and 360959 columns
Presolve time: 1.39s
Presolved: 19954 rows, 67733 columns, 162602 nonzeros
Found heuristic solution: objective 3.395001e+09
Variable types: 51821 continuous, 15912 integer (15912 binary)
Found heuristic solution: objective 3.396465e+09
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...Concurrent spin time: 0.00s
Solved with dual simplex
Extra simplex iterations after uncrush: 62Root relaxation: objective 7.425405e+09, 3724 iterations, 0.09 seconds (0.16 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 7.4254e+09 0 1003 3.3965e+09 7.4254e+09 119% - 1s
H 0 0 7.298411e+09 7.4254e+09 1.74% - 1s
H 0 0 7.745011e+09 7.7450e+09 -0.00% - 1s
0 0 7.4254e+09 0 1003 7.7450e+09 7.7450e+09 -0.00% - 1sExplored 1 nodes (5067 simplex iterations) in 1.75 seconds (2.44 work units)
Thread count was 12 (of 12 available processors)Solution count 5: 7.74501e+09 7.29841e+09 3.39647e+09 ... -7.47932e+07
Optimal solution found (tolerance 1.00e-04)
Best objective 7.150488608911e+09, best bound 7.745010513334e+09, gap 8.3144%User-callback calls 887, time in user-callback 0.00 sec
0 -
Hi Hector,
Since you are a commercial customer with us we will handle this as a Support Request. Your colleague Vladimir submitted such a request related to this problem so we will communicate with you both through that channel.
Kind Regards,
Riley0
Please sign in to leave a comment.
Comments
12 comments