Limit Presolving Time

[Lukas Barth]

Hi,

I'm currently solving models with a time limit of 10 minutes, and the solving often hits the time limit. This is expected and okay. However, I notice that often, the time limit is already reached during presolving. Is there any way of limiting the time spent during presolve? There are two reasons I want to do that: First, it looks like the last 70% of the presolving are very inefficient: Most of the rows / columns are removed within the first 30 seconds, after that, very little progress is made in the remaining 570 seconds, and it would probably be more efficient to start the actual solving. Second, in cases where solving is not possible within 10 minutes, it would be nice to at least have an upper bound - but for that, the actual solver must find such a bound..

I tried setting PrePasses, but the "passes" seem not to correspond to the lines of output gurobi produces.. i.e. setting a low value for "PrePasses" still results in presolving running into the time limit.

Is there anything else I can limit?

Thanks in advance,

Lukas

[Tobias Achterberg]

You can set the "Presolve" parameter to 1 to use it more conservatively.
The log output does not correspond to the passes. We just print some message
every 5 seconds (if we hit the places often enough where we would print a message).

I would be interested in looking at your models to find out which part of the
presolver takes such a long time. Maybe there is some undocumented parameter
that you can set to turn off this specific reduction.

Would you be willing to provide one (or a few) models, preferably in MPS file
format? If they are not terribly large, you can send them to achterberg (at)
gurobi (dot) com. Otherwise, I can provide a way to upload them to our website.


Thanks,

Tobias

[Lukas Barth]

Hi Tobias,

On Monday, June 20, 2016 at 2:19:21 PM UTC+2, Tobias Achterberg wrote:

You can set the "Presolve" parameter to 1 to use it more conservatively.

I'm trying that now, let's see if it helps.

 

I would be interested in looking at your models to find out which part of the
presolver takes such a long time. Maybe there is some undocumented parameter
that you can set to turn off this specific reduction.

Here are two models that (for me) take > 600 seconds in presolving:

http://i11www.iti.uni-karlsruhe.de/~barth/problem-AM1.mps

http://i11www.iti.uni-karlsruhe.de/~barth/problem-AM3.mps

They are both rather huge (> 6GB), but presolving actually does a very good job at reducing them (see below). 

Please note that I'm trying to solve these with Aggregate=0, as per https://groups.google.com/forum/#!topic/gurobi/JJl0ptJZwzE ...

Here is the output of a session trying to solve one of those models:

gurobi> m = read("/tmp/problem-AM3.mps")
mgurobi> m.setParam("Aggregate", 0)
Changed value of parameter Aggregate to 0
   Prev: 1   Min: 0   Max: 1   Default: 1
gurobi> m.setParam("TimeLimit", 600)
Changed value of parameter TimeLimit to 600.0
   Prev: 1e+100   Min: 0.0   Max: 1e+100   Default: 1e+100
gurobi> m.optimize()
Optimize a model with 56757788 rows, 41153940 columns and 119829234 nonzeros
Coefficient statistics:
  Matrix range    [1e-11, 1e+01]
  Objective range [1e-11, 3e-02]
  Bounds range    [1e+00, 1e+00]
  RHS range       [6e-04, 1e+00]
Found heuristic solution: objective 0
Presolve removed 0 rows and 0 columns (presolve time = 6s) ...
Presolve removed 4157484 rows and 918 columns (presolve time = 11s) ...
Presolve removed 50644587 rows and 39025089 columns (presolve time = 19s) ...
Presolve removed 50644587 rows and 39025089 columns (presolve time = 22s) ...
Presolve removed 52820059 rows and 39025136 columns (presolve time = 25s) ...
Presolve removed 53069540 rows and 39025136 columns (presolve time = 30s) ...
Presolve removed 53070507 rows and 39025780 columns (presolve time = 37s) ...
Presolve removed 53070507 rows and 39025780 columns (presolve time = 40s) ...
Presolve removed 53070595 rows and 39025827 columns (presolve time = 45s) ...
Presolve removed 53071134 rows and 39026117 columns (presolve time = 50s) ...
Presolve removed 53071836 rows and 39026544 columns (presolve time = 55s) ...
Presolve removed 53072473 rows and 39026872 columns (presolve time = 61s) ...
Presolve removed 53072488 rows and 40824264 columns (presolve time = 537s) ...
Presolve removed 53072488 rows and 40824264 columns (presolve time = 540s) ...
Presolve removed 53072488 rows and 41091421 columns (presolve time = 548s) ...
Presolve removed 53072488 rows and 41091421 columns (presolve time = 550s) ...
Presolve removed 53101926 rows and 41091595 columns (presolve time = 556s) ...
Presolve removed 53145043 rows and 41091678 columns (presolve time = 560s) ...
Presolve removed 53183493 rows and 41091795 columns (presolve time = 565s) ...
Presolve removed 53183493 rows and 41091795 columns (presolve time = 570s) ...
Presolve removed 53183493 rows and 41092212 columns (presolve time = 579s) ...
Presolve removed 53183493 rows and 41092212 columns (presolve time = 580s) ...
Presolve removed 53183493 rows and 41092219 columns (presolve time = 586s) ...
Presolve removed 55248314 rows and 41092355 columns
Presolve time: 595.17s
Explored 0 nodes (0 simplex iterations) in 602.46 seconds
Thread count was 1 (of 4 available processors)
Time limit reached
Best objective 0.000000000000e+00, best bound -, gap -

As you can see, presolve removes 90% of the rows and columns within the first 30 seconds, but then keeps going for another 10 minutes without any significant progress. Also note that there is a huge gap between the output at 61 seconds and the next line at 537 seconds - whatever gurobi has been doing there took a very long time and blocked the loop that produces the output..

I'm using Gurobi 6.0 here. I could try with Gurobi 6.5, but that would be tricky, since the only machine I have 6.5 running on (my laptop...) has trouble with these rather large models.

By the way: thanks for the super-fast and competent responses. :) That's not a service level I'm used to as a "free-riding" academic user.

Lukas

[Tobias Achterberg]

Hi Lukas,

it seems that Gurobi 6.5 is much better on this. I get the following for your
"problem-AM3.mps" model on an Intel Xeon CPU E3-1240 v5 @ 3.50GHz:

Presolve removed 4157484 rows and 2071146 columns (presolve time = 82s) ...
Presolve removed 52710696 rows and 41090824 columns (presolve time = 85s) ...
Presolve removed 56563372 rows and 41091034 columns (presolve time = 90s) ...
Presolve removed 56626496 rows and 41093937 columns (presolve time = 95s) ...
Presolve removed 56639538 rows and 41095139 columns (presolve time = 100s) ...
Presolve removed 56640091 rows and 41095254 columns (presolve time = 105s) ...
Presolve removed 56640154 rows and 41095316 columns (presolve time = 147s) ...
Presolve removed 56640154 rows and 41095316 columns (presolve time = 150s) ...
Presolve removed 56640154 rows and 41095631 columns (presolve time = 155s) ...
Presolve removed 56641037 rows and 41095927 columns (presolve time = 161s) ...
Presolve removed 56641045 rows and 41095933 columns (presolve time = 166s) ...
Presolve removed 56647200 rows and 41099816 columns (presolve time = 172s) ...
Presolve removed 56647200 rows and 41099816 columns
Presolve time: 171.60s

...


Explored 1029 nodes (333082 simplex iterations) in 436.37 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective -2.749045605080e+01, best bound -2.749255699089e+01, gap 0.0076%


So, I guess you should, if possible, invest the work to upgrade to Gurobi 6.5.


Best regards,

Tobias