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ł -
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
-
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. -
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.
-
It seems to be an output error. Setting NumericFocus=1 or Presolve=2 seems to be a valid workaround. Thank you for reporting this.
-
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.
-
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.
Please sign in to leave a comment.
Comments
10 comments