Bug Report: Incorrect result for MIQP
Answered
The linked LP file contains a relatively small MIQP example that Gurobi 8.1.0 produces an incorrect result for. When solved with parameter settings left at their defaults, Gurobi produces an optimal objective of 1, and claims the best bound is also 1. However, the optimal objective is 0. Gurobi does find the correct result when presolve is disabled.
Sorry, but I am away from my academic institution, so I am unable to update Gurobi to test the latest version (8.1.1).
LP file: https://gist.github.com/ghackebeil/45435a44df47972444e4b681e64f7f21
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Gabriel,
my gurobi solves your model with objective 0. I've tested 8.1.0 and 8.1.1 - both yield the same (correct) result.
Which platform do you use?Gurobi Optimizer version 8.1.0 build v8.1.0rc1 (win64)
Copyright (c) 2018, Gurobi Optimization, LLC
Read LP format model from file buggy_gurobi_example.lp
Reading time = 0.01 seconds
: 111 rows, 306 columns, 956 nonzeros
Optimize a model with 111 rows, 306 columns and 956 nonzeros
Model has 5 quadratic objective terms
Variable types: 56 continuous, 250 integer (250 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+01]
Objective range [2e+01, 6e+03]
QObjective range [2e+00, 2e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 3899.0000000
Presolve removed 51 rows and 51 columns
Presolve time: 0.02s
Presolved: 60 rows, 255 columns, 650 nonzeros
Presolved model has 5 quadratic objective terms
Variable types: 0 continuous, 255 integer (250 binary)
Root relaxation: objective 0.000000e+00, 85 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 5 3899.00000 0.00000 100% - 0s
H 0 0 157.0000000 0.00000 100% - 0s
0 0 0.00000 0 8 157.00000 0.00000 100% - 0s
0 0 0.00000 0 8 157.00000 0.00000 100% - 0s
H 0 0 66.0000000 0.00000 100% - 0s
H 0 1 58.0000000 0.00000 100% - 0s
0 1 0.00000 0 4 58.00000 0.00000 100% - 0s
H 30 10 26.0000000 0.00000 100% 5.1 0s
H 65 13 14.0000000 0.00000 100% 4.6 0s
H 115 12 4.0000000 0.00000 100% 4.2 0s
* 139 3 82 0.0000000 0.00000 0.00% 4.1 0s
Explored 165 nodes (745 simplex iterations) in 0.22 seconds
Thread count was 4 (of 4 available processors)
Solution count 8: 0 4 14 ... 3899
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
=============================================================================Gurobi Optimizer version 8.1.1 build v8.1.1rc0 (win64)
Copyright (c) 2019, Gurobi Optimization, LLC
Read LP format model from file buggy_gurobi_example.lp
Reading time = 0.00 seconds
: 111 rows, 306 columns, 956 nonzeros
Optimize a model with 111 rows, 306 columns and 956 nonzeros
Model has 5 quadratic objective terms
Variable types: 56 continuous, 250 integer (250 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+01]
Objective range [2e+01, 6e+03]
QObjective range [2e+00, 2e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 3899.0000000
Presolve removed 51 rows and 51 columns
Presolve time: 0.01s
Presolved: 60 rows, 255 columns, 650 nonzeros
Presolved model has 5 quadratic objective terms
Variable types: 0 continuous, 255 integer (250 binary)
Root relaxation: objective 0.000000e+00, 85 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 5 3899.00000 0.00000 100% - 0s
H 0 0 157.0000000 0.00000 100% - 0s
0 0 0.00000 0 8 157.00000 0.00000 100% - 0s
0 0 0.00000 0 8 157.00000 0.00000 100% - 0s
H 0 0 66.0000000 0.00000 100% - 0s
H 0 1 58.0000000 0.00000 100% - 0s
0 1 0.00000 0 4 58.00000 0.00000 100% - 0s
H 30 10 26.0000000 0.00000 100% 5.1 0s
H 65 13 14.0000000 0.00000 100% 4.6 0s
H 115 12 4.0000000 0.00000 100% 4.2 0s
* 139 3 82 0.0000000 0.00000 0.00% 4.1 0s
Explored 165 nodes (745 simplex iterations) in 0.19 seconds
Thread count was 4 (of 4 available processors)
Solution count 8: 0 4 14 ... 3899
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%0 -
Hi Gabriel,
I can reproduce the inconsistent 0/1 objective value termination. We will figure out what is going on, thanks for reporting!
0 -
Hello Gabriel, we have fixed the problem, and the fix will be included in the next Gurobi release.
0 -
Great to hear!
For completeness, added below is my reply to the first comment, which didn't make it to this forum because I replied through email:
Hi Jakob,
That’s good to hear, perhaps it’s been fixed. I’m on macOS Mojave 10.14.4. Attached is some log output showing the issue occurring on my system, and how it stops occurring if presolve is disabled. Also attaching the LP file again, just in case it somehow doesn’t match what is in the link I posted.
Comparing my "8.1.0 build v8.1.0rc1” output with yours, it looks like the main platform differences are Windows, 4 threads (you) and macOS, 8 threads (me). I went ahead and investigated the threads setting, and (leaving presolve enabled) it looks like Gurobi gets the correct answer on my machine if I set the number of threads to 1,2, or 3. Anything higher, and it returns 1 for the optimal value instead of 0.
Gabe
0
Post is closed for comments.
Comments
5 comments