Proof of infeasibility for MILP

[Marek Tyburec]

Dear all,

I have a very large-scale MILP problem for which I know a very good solution, which could be even globally-optimal. The task is either to (i) prove the global optimality, or to (ii) find the global optimum.
In order to manage the binary tree size that needs to be stored, I manually split (branched) the problem into several smaller subproblems, for which I set the Cutoff parameter corresponding to the known solution. Therefore, most of the subproblems should be infeasible. Also, I turned off heuristics and set a time limit.

Evaluating such strategy, I ended with the following log, from which it implies that the solver explored the whole binary tree in something above 80 s, however, the Gurobi process hanged until the time limit of 172700 s passed. The question is then - how to make the process quit after exploring the whole tree (and thus proving infeasibility)?

Marek T.

Gurobi 7.0.0 (linux64) logging started Mon Nov 21 15:09:41 2016

Set parameter LogFile to value example_72bar32_15.log
Set parameter TimeLimit to value 172700
Optimize a model with 18746 rows, 5216 columns and 107968 nonzeros
Variable types: 4704 continuous, 512 integer (448 binary)
Coefficient statistics:
  Matrix range     [7e-02, 5e+02]
  Objective range  [2e+00, 3e+02]
  Bounds range     [2e-01, 8e+01]
  RHS range        [2e-01, 3e+02]
Presolve removed 7163 rows and 1857 columns
Presolve time: 0.34s
Presolved: 11583 rows, 3359 columns, 61361 nonzeros

MIP start did not produce a new incumbent solution

Variable types: 2976 continuous, 383 integer (383 binary)
Presolved: 11583 rows, 3359 columns, 61361 nonzeros


Root relaxation: objective 3.187400e+02, 9444 iterations, 1.00 seconds

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

     0     0  318.73999    0   13          -  318.73999      -     -    1s
Another try with MIP start
     0     0  318.96595    0   12          -  318.96595      -     -    2s
     0     0  318.96595    0   11          -  318.96595      -     -    3s
     0     0  319.10382    0   12          -  319.10382      -     -    3s
     0     0  319.10856    0   12          -  319.10856      -     -    3s
     0     0  319.16013    0   12          -  319.16013      -     -    3s
     0     0  319.16157    0   12          -  319.16157      -     -    3s
     0     0  319.55803    0   17          -  319.55803      -     -    3s
     0     0  319.61191    0   16          -  319.61191      -     -    3s
     0     0  319.66763    0   16          -  319.66763      -     -    4s
     0     0  319.66784    0   16          -  319.66784      -     -    4s
     0     2  319.66784    0   16          -  319.66784      -     -    5s
   467   287  381.48794   15    9          -  331.57486      -   354   10s
  1759  1068  364.19072   35   15          -  345.72152      -   274   15s
  2545  1590  347.57070   13   10          -  347.57070      -   270   20s
  2879  1719  378.47519   23    6          -  347.57070      -   299   25s
  4677  2078     cutoff   23               -  354.71607      -   270   30s
  7042  2358  367.21009   21   14          -  360.33139      -   245   35s
  9739  3443     cutoff   22               -  363.44264      -   233   40s
 12615  4072  378.55515   26   20          -  366.99381      -   232   45s
 15176  4812     cutoff   53               -  369.07093      -   230   50s
 17672  5472  381.73548   27   11          -  370.74942      -   226   55s
 19955  5923  380.62652   24    4          -  372.29292      -   223   60s
 22431  5939  378.84120   27    6          -  373.88167      -   220   65s
 25091  5363  378.95398   23   11          -  376.22773      -   217   70s
 28166  3812     cutoff   56               -  379.53722      -   213   75s
 31059  1373     cutoff   34               -  383.10111      -   206   80s

Cutting planes:
  Gomory: 2
  Cover: 2
  Projected Implied bound: 22
  MIR: 7
  Flow cover: 46
  Inf proof: 4

Explored 32972 nodes (6574727 simplex iterations) in 172700.01 seconds
Thread count was 24 (of 24 available processors)

Solution count 0
Pool objective bound 385.543

Time limit reached
Best objective -, best bound 3.855426650800e+02, gap -

Warning: unable to write requested result file 'example_72bar32_15.sol'

[Sonja Mars]

Hi Marek,

This behavior is not normal. We would like to investigate what is going on. Can you share the model file with us (please compress it or put it in a dropbox or so)? If you cannot share it with the group, can you send it to support[at]gurobi[dot]com?

Thanks and best regards,
Sonja


----
Dr. Sonja Mars
Gurobi Optimization - Technical Support

[Marek Tyburec]

Thank you for your fast response,

I attach a minimal working example here. The zip file contains example_72bar.py file that I used for launching the optimization; you will need to modify the python path there. Also, for this specific problem the solution file does not provide a feasible solution. However, commenting that line does not have any effect.

https://drive.google.com/file/d/0B6DmI4pi_rn5Uzl3TWNoRGFkT28/view?usp=sharing



Dne pátek 21. dubna 2017 13:24:52 UTC+2 Sonja Mars napsal(a):

[Marek Tyburec]

Dear Sonja Mars,

are there any news regarding the investigation? I know that me, as an academic user, am not provided with the official support from Gurobi. However, as I do actually need to continue my work, I have only these possibilities - either wait for your investigation, or to use another software such as cplex. Would it be please possible to inform me, how long is (or if) the investigation going to take?

Kind regards,

Marek Tyburec

Dne pátek 21. dubna 2017 15:30:28 UTC+2 Marek Tyburec napsal(a):

[Sonja Mars]

Hi,

Sorry for the delay in responding. 

I was able to reproduce the behavior you are reporting. I am currently not sure what is exactly happening. I will pass this along to our developers. 

In the meantime as a workaround can you use the default values of MIPGap and MIPGapAbs? Then the run should go fine and finish soon. This is the result on my machine:

Explored 52 nodes (20096 simplex iterations) in 5.53 seconds
Thread count was 8 (of 8 available processors)

Solution count 0
Pool objective bound 385.543

Model objective exceeds cutoff

Best objective -, best bound 3.855430000000e+02, gap -

Setting MIPGap and MIPGapAbs to zero makes it always very hard for the solver to converge and we don't recommend setting those to zero. 

I hope this helps you for your experiments. 

Best regards, 

[Marek Tyburec]

Hi,

thank you for your kind response. Unfortunately, setting MIPGap and MIPGapAbs to default values is inappropriate for our specific case, as we search a proven globally optimal solution; thus, we need to eliminate the whole tree below the cuttoff value. Otherwise, there would always be a gap where better solutions might lie.

Therefore, I currently switched to CPLEX, as it in this case behaves well, and look forward to have this issue fixed in the next gurobi release :-).

Best regards,

Marek

Dne úterý 9. května 2017 9:56:48 UTC+2 Sonja Mars napsal(a):

[Sonja Mars]

Hi Marek,

Our developers identified an issue that will be fixed in our next release. Thanks for reporting this.

As a work-around, you can set the MIPGapAbs parameter to a tiny positive value like 1e-100. This will trigger the part of the code that then aborts the computation.

Thanks again and best regards,
Sonja