9

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!

Legsleg
  • 153
  • 7
  • Perhaps you can show the solver logs. – Mark L. Stone Jul 07 '22 at 11:32
  • I added the output of Gurobi to my post. – Legsleg Jul 07 '22 at 11:56
  • 1
    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 07 '22 at 13:22
  • 2
    I read the .lp file CPLEX and was able to solve it (Objective = $1.0275000000e+04$). So indeed, this is Gurobi related. – Kuifje Jul 07 '22 at 14:51
  • I too got the correct solution with CPLEX. I had it compute kappa statistics (condition numbers), and it reported 100% stable bases with a maximum condition number around 7e+4 (which is usually not big enough to trip up a solver). You might try experimenting with presolve settings (such as symmetry detection) to see if maybe the presolver made a mistake. – prubin Jul 07 '22 at 15:32
  • The problem still remains when completely deactivating the presolver (with env.setParam('Presolve', 0)) so it doesn't seem to be the problem. – Legsleg Jul 07 '22 at 17:18
  • Adding the optimal solution as MIP start results in Gurobi correctly returning this solution. In fact enforcing the solution through equality constraints now also causes Gurobi returning this solution. I can't explain why this wasn't the case earlier today. I crossed out the corresponding part in my post. – Legsleg Jul 07 '22 at 17:28
  • 1
    I am having a look right now (I work for Gurobi) – Richard Jul 08 '22 at 07:33
  • 4
    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. – Richard Jul 08 '22 at 10:27
  • 1
    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.

     – Ed Klotz Jul 11 '22 at 20:16
  • @Legsleg 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. – David Torres Dec 20 '22 at 12:25

2 Answers2

6

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!

Legsleg
  • 153
  • 7
6

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.

Ed Klotz
  • 161
  • 2