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 -
-
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 -
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
Please sign in to leave a comment.
Comments
6 comments