9
$\begingroup$

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!

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sune
    Jul 7, 2022 at 13:22
  • 2
    $\begingroup$ I read the .lp file CPLEX and was able to solve it (Objective = $1.0275000000e+04$). So indeed, this is Gurobi related. $\endgroup$
    – Kuifje
    Jul 7, 2022 at 14:51
  • 1
    $\begingroup$ I am having a look right now (I work for Gurobi) $\endgroup$
    – Richard
    Jul 8, 2022 at 7:33
  • 4
    $\begingroup$ 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. $\endgroup$
    – Richard
    Jul 8, 2022 at 10:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ed Klotz
    Jul 11, 2022 at 20:16

2 Answers 2

6
$\begingroup$

Here's a further suggestion.

The Gurobi developers are looking into this. Based on what they have found so far, setting the InfProofCuts parameter to 0 will avoid the problem consistently. This is a more robust workaround than setting the MIPFocus parameter to 1, which does change the intensity with which Gurobi applies cuts, but I don't think it guarantees that the InfProofCuts will not be applied.

Hopefully this is somewhat more satisfactory. We'll update when we have a better idea of what happened with these cuts on this model.

$\endgroup$
2
  • $\begingroup$ Yes, it indeed is, thank you for the additional information! $\endgroup$
    – Legsleg
    Jul 12, 2022 at 16:39
  • 1
    $\begingroup$ The bug relating to infeasibility proof cuts affecting this model has been fixed with Gurobi 10.0.0. You no longer have to set InfProofCuts to 0. $\endgroup$ Dec 20, 2022 at 12:27
6
$\begingroup$

Setting the Parameter MIPFocus to 1 (described in the documentation as putting a bigger focus on finding feasible solutions instead of proving optimality) solves the problem (at least for this specific instance).

Although it feels a bit unsatisfactory since it doesn't really explain the problem I will settle for this solution for the time being (as long as there are no further suggestions) and add some more safety nets to my surrounding implementation. Thank you for your input!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.