Bug report: infeasible with 1 thread
Answered
Infeasibility reported when solving with 1 thread, but without the thread option, a feasible solution is found in 1 second. Platform: Debian 9.9, i7-4771
Instance: https://www.dropbox.com/s/v8h1obsod9iyr1q/road_naive_11.mps.gz?dl=0
Feasible call: /opt/gurobi811/linux64/bin/gurobi_cl IntFeasTol=1e-8 MIPGap=1e-8 road_naive_11.mps.g
z (this model needs tight tolerances due do big-M constraints)
Infeasible call: /opt/gurobi811/linux64/bin/gurobi_cl IntFeasTol=1e-8 MIPGap=1e-8 Threads=1 road_naiv
e_11.mps.gz
Output:
Academic license - for non-commercial use only
Set parameter IntFeasTol to value 1e-8
Set parameter MIPGap to value 1e-8
Set parameter Threads to value 1
Gurobi Optimizer version 8.1.1 build v8.1.1rc0 (linux64)
Copyright (c) 2019, Gurobi Optimization, LLC
Read MPS format model from file road_naive_11.mps
Reading time = 0.06 seconds
mzn_gurobi: 20878 rows, 16012 columns, 53983 nonzeros
Optimize a model with 20878 rows, 16012 columns and 53983 nonzeros
Variable types: 8221 continuous, 7791 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+07]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 6e+07]
RHS range [1e+00, 1e+07]
Presolve removed 12677 rows and 11597 columns
Presolve time: 0.07s
Presolved: 8201 rows, 4415 columns, 29655 nonzeros
Variable types: 0 continuous, 4415 integer (3875 binary)
Root relaxation: objective 4.000000e+00, 928 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 8.00000 0 63 - 8.00000 - - 0s
0 0 8.00000 0 277 - 8.00000 - - 0s
0 0 8.00000 0 292 - 8.00000 - - 0s
0 0 8.00000 0 86 - 8.00000 - - 0s
0 0 8.00000 0 110 - 8.00000 - - 0s
0 0 8.00000 0 107 - 8.00000 - - 0s
0 0 8.00000 0 153 - 8.00000 - - 0s
0 0 8.00000 0 109 - 8.00000 - - 0s
0 0 8.00000 0 97 - 8.00000 - - 0s
0 2 8.00000 0 95 - 8.00000 - - 1s
520 440 226.00000 206 141 - 226.00000 - 55.6 5s
582 483 226.00000 35 206 - 226.00000 - 41.3 10s
1006 727 infeasible 154 - 226.00000 - 52.5 15s
1695 831 226.00000 222 141 - 226.00000 - 60.4 20s
2660 1072 infeasible 228 - 226.00000 - 64.4 25s
3703 1473 infeasible 234 - 226.00000 - 62.9 30s
4633 1930 infeasible 238 - 226.00000 - 59.8 35s
5252 2404 652.00000 223 156 - 226.00000 - 57.5 40s
5843 2883 infeasible 207 - 226.00000 - 57.5 45s
6651 3491 652.00000 101 238 - 226.00000 - 56.5 50s
7157 3907 335.00000 43 181 - 226.00000 - 58.7 55s
7864 4458 226.00000 29 206 - 226.00000 - 58.2 60s
8967 5271 2000595.00 237 184 - 226.00000 - 55.6 65s
10097 6004 1064.00000 235 261 - 226.00000 - 53.0 70s
10203 6066 226.00000 38 97 - 226.00000 - 53.2 96s
10211 6071 650.00000 222 385 - 296.00000 - 53.2 100s
10217 6075 903.00000 44 317 - 297.00000 - 53.1 105s
10224 6080 804.00000 233 206 - 297.00011 - 53.1 110s
Cutting planes:
Learned: 1
Gomory: 1
Cover: 32
Implied bound: 48
Clique: 4
MIR: 1
Flow cover: 112
Explored 10226 nodes (609233 simplex iterations) in 111.82 seconds
Thread count was 1 (of 8 available processors)
Solution count 0
Model is infeasible
Best objective -, best bound -, gap -
-
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 Gleb,
I am guessing that the problems comes from the fact that you are using a tighter tolerance for integer feasibility than for primal feasibility.... I did run your model with a tighter primal feasibility (1e-9) and got solutions without problem. Note however that for this model it does not seem that you need tighter tolerances at al!
0 -
Greg GlocknerGurobi Staff
In general, whenever you get an infeasible model, it is useful to run IIS, to understand why it is infeasible.
0 -
Hi Daniel and Greg,
@Daniel: what do you mean by primal feasibility? Running IntFeasTol=1e-8 MIPGap=1e-9 Threads=1 gives infeasible as well, however IntFeasTol=1e-9 MIPGap=1e-8 Threads=1 finds solutions. I don't remember hearing about relation of absolute/relative objective gap to integrality tolerance. Would be grateful for an explanation and what parameters you recommend when using tighter IntFeasTol.
@Greg: I stopped IIS after over 1h, it still had 20000 constraints and 30000 bounds. But if this result is due to (numerical?) instability, what can IIS tell us?
@Daniel: this instance does need tighter tolerance because it has constraints like X = 200c + 1000000(1-c) where c is binary, meaning (c=1 -> X=200) /\ (c=0 -> X=1000000). Obviously not good modeling but the question is why the solver behaves differently depending on the number of threads. Just numerical problems?
0 -
Hi Gleb,
I meant the relation between IntFeasTol and FeasibilityTol, and it should be that IntFeasTol >= FeasibilityTol.
Also, regarding the large numbers.... did you test that if using default parameters you got solutions that could not be trusted?
0 -
Hi Daniel,
the advice that it should be that IntFeasTol >= FeasibilityTol appears more familiar to me but still I'd found it helpful to have it reminded in the descriptions of those parameters.
Yes I tested several instances of this model, which is the "road-construction" from MiniZinc Challenge 2014. Solution checker rounds the value of c, see the example above. When you have c=0.999999, which is feasible with default tolerance, the MIP solution has X~201 but the MiniZinc solution checker recomputes it from X = 200c + 1000000(1-c) with c=1 and obtains a contradiction.
0 -
Hi Gleb,
Sure, we will update the docs in that regard.... now, numerics is a tricky area... and sometimes the numbers just don't add up, defining what truly is a wrong answer and a right one is not as easy as it might seem
Best regards,
Daniel
0
Post is closed for comments.
Comments
7 comments