# Gurobi finishes with 'infeasible' although optimal solution exists

I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs.

I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the vertices connected through an outgoing edge is at most the sum of weights put on the vertices connected through ingoing edges. It can be proven that there exists a single such weighting for any tournament.

Still I encountered problems with a tournament on 15 vertices, which induces the following optimization problem:

\ Model BP-solver
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
vertices[0] + vertices[1] + vertices[2] + vertices[3] + vertices[4]
+ vertices[5] + vertices[6] + vertices[7] + vertices[8] + vertices[9]
+ vertices[10] + vertices[11] + vertices[12] + vertices[13]
+ vertices[14]
Subject To
optimality_of_node[0]: vertices[1] - vertices[2] + vertices[3]
- vertices[4] + vertices[5] - vertices[6] + vertices[7] - vertices[8]
- vertices[9] + vertices[10] - vertices[11] - vertices[12]
+ vertices[13] + vertices[14] <= 0
optimality_of_node[1]: - vertices[0] - vertices[2] + vertices[3]
+ vertices[4] + vertices[5] - vertices[6] + vertices[7] + vertices[8]
- vertices[9] + vertices[10] + vertices[11] + vertices[12]
- vertices[13] - vertices[14] <= 0
optimality_of_node[2]: vertices[0] + vertices[1] - vertices[3]
+ vertices[4] - vertices[5] + vertices[6] + vertices[7] + vertices[8]
+ vertices[9] - vertices[10] + vertices[11] - vertices[12]
- vertices[13] - vertices[14] <= 0
optimality_of_node[3]: - vertices[0] - vertices[1] + vertices[2]
- vertices[4] + vertices[5] - vertices[6] + vertices[7] + vertices[8]
+ vertices[9] + vertices[10] - vertices[11] - vertices[12]
- vertices[13] - vertices[14] <= 0
optimality_of_node[4]: vertices[0] - vertices[1] - vertices[2]
+ vertices[3] - vertices[5] + vertices[6] - vertices[7] - vertices[8]
+ vertices[9] + vertices[10] + vertices[11] - vertices[12]
- vertices[13] + vertices[14] <= 0
optimality_of_node[5]: - vertices[0] - vertices[1] + vertices[2]
- vertices[3] + vertices[4] - vertices[6] + vertices[7] - vertices[8]
- vertices[9] - vertices[10] + vertices[11] + vertices[12]
- vertices[13] + vertices[14] <= 0
optimality_of_node[6]: vertices[0] + vertices[1] - vertices[2]
+ vertices[3] - vertices[4] + vertices[5] + vertices[7] - vertices[8]
+ vertices[9] - vertices[10] - vertices[11] + vertices[12]
+ vertices[13] - vertices[14] <= 0
optimality_of_node[7]: - vertices[0] - vertices[1] - vertices[2]
- vertices[3] + vertices[4] - vertices[5] - vertices[6] + vertices[8]
+ vertices[9] + vertices[10] - vertices[11] + vertices[12]
+ vertices[13] + vertices[14] <= 0
optimality_of_node[8]: vertices[0] - vertices[1] - vertices[2]
- vertices[3] + vertices[4] + vertices[5] + vertices[6] - vertices[7]
+ vertices[9] - vertices[10] - vertices[11] + vertices[12]
- vertices[13] + vertices[14] <= 0
optimality_of_node[9]: vertices[0] + vertices[1] - vertices[2]
- vertices[3] - vertices[4] + vertices[5] - vertices[6] - vertices[7]
- vertices[8] + vertices[10] + vertices[11] - vertices[12]
+ vertices[13] + vertices[14] <= 0
optimality_of_node[10]: - vertices[0] - vertices[1] + vertices[2]
- vertices[3] - vertices[4] + vertices[5] + vertices[6] - vertices[7]
+ vertices[8] - vertices[9] + vertices[11] + vertices[12] + vertices[13]
- vertices[14] <= 0
optimality_of_node[11]: vertices[0] - vertices[1] - vertices[2]
+ vertices[3] - vertices[4] - vertices[5] + vertices[6] + vertices[7]
+ vertices[8] - vertices[9] - vertices[10] - vertices[12] + vertices[13]
+ vertices[14] <= 0
optimality_of_node[12]: vertices[0] - vertices[1] + vertices[2]
+ vertices[3] + vertices[4] - vertices[5] - vertices[6] - vertices[7]
- vertices[8] + vertices[9] - vertices[10] + vertices[11] + vertices[13]
- vertices[14] <= 0
optimality_of_node[13]: - vertices[0] + vertices[1] + vertices[2]
+ vertices[3] + vertices[4] + vertices[5] - vertices[6] - vertices[7]
+ vertices[8] - vertices[9] - vertices[10] - vertices[11] - vertices[12]
+ vertices[14] <= 0
optimality_of_node[14]: - vertices[0] + vertices[1] + vertices[2]
+ vertices[3] - vertices[4] - vertices[5] + vertices[6] - vertices[7]
- vertices[8] - vertices[9] + vertices[10] - vertices[11] + vertices[12]
- vertices[13] <= 0
non_zero_solution: vertices[0] + vertices[1] + vertices[2] + vertices[3]
+ vertices[4] + vertices[5] + vertices[6] + vertices[7] + vertices[8]
+ vertices[9] + vertices[10] + vertices[11] + vertices[12]
+ vertices[13] + vertices[14] >= 1
Bounds
Generals
vertices[0] vertices[1] vertices[2] vertices[3] vertices[4] vertices[5]
vertices[6] vertices[7] vertices[8] vertices[9] vertices[10] vertices[11]
vertices[12] vertices[13] vertices[14]
End


For this problem, Gurobi concludes infeasibility with the following output:

Optimize a model with 16 rows, 15 columns and 225 nonzeros
Model fingerprint: 0x32656352
Variable types: 0 continuous, 15 integer (0 binary)
Coefficient statistics:
Matrix range     [1e+00, 1e+00]
Objective range  [1e+00, 1e+00]
Bounds range     [0e+00, 0e+00]
RHS range        [1e+00, 1e+00]
Presolve time: 0.00s
Presolved: 16 rows, 15 columns, 225 nonzeros
Variable types: 0 continuous, 15 integer (0 binary)

Root relaxation: objective 1.000000e+00, 19 iterations, 0.00 seconds (0.00 work units)

Nodes    |    Current Node    |     Objective Bounds      |     Work
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

0     0    1.00000    0   15          -    1.00000      -     -    0s
0     0   34.83051    0   14          -   34.83051      -     -    0s
0     0  264.55687    0   15          -  264.55687      -     -    0s
0     0  642.18750    0   15          -  642.18750      -     -    0s
0     1  642.18750    0   15          -  642.18750      -     -    0s

Cutting planes:
Inf proof: 1

Explored 806 nodes (1476 simplex iterations) in 0.09 seconds (0.03 work units)
Thread count was 8 (of 8 available processors)

Solution count 0

Model is infeasible
Best objective -, best bound -, gap -


When running model.feasRelaxS(1, False, False, True) before optimization and rounding the results I get the solution that fulfils all constraints (I checked manually).

The expected weighting is [1245, 339, 1515, 519, 249, 495, 295, 705, 721, 449, 993, 377, 909, 329, 1135].

I tried enforcing these values by adding them as additional equality constraints, but this still leaves the model infeasible without relaxation and with relaxation leads to a solution that is wildly off.

I cannot make sense of Gurobis behaviour and feel like I am either missing something obvious or am facing a quirk for which I don't nearly know enough about the technical details of Gurobi to understand. So if you have any idea, I would really appreciate any tips on what might be causing this behaviour!

• Try to add your known feasible solution as a MIP start to the solver and see what happens. Or fix your variables to your known values, and hit "solve". That way you can probably see what constraints GUROBI thinks you are violating.
– Sune
Jul 7, 2022 at 13:22
• I read the .lp file CPLEX and was able to solve it (Objective = $1.0275000000e+04$). So indeed, this is Gurobi related. Jul 7, 2022 at 14:51
• I am having a look right now (I work for Gurobi) Jul 8, 2022 at 7:33
• I can reproduce this, and it looks like by switching off Cuts (through Cuts=0) we find the optimal solution. I have escalated this to the development team and will let you know when I know more. Jul 8, 2022 at 10:27
• As my colleague Richard indicated, the Gurobi dev team is looking at this. They have isolated the specific cut that should be switched off; it showed up in the log file of the problematic infeasible run: Cutting planes: Inf proof: 1 So rather than disabling all cuts, just disable the infeasibility proof cuts: m.setParam("InfProofCuts", 0) We'll let you know when we have more info. Jul 11, 2022 at 20:16