0
$\begingroup$

I have a small model to optimize in Gurobi. The problem is that it takes a lot of time in presolve without removing any rows or variables. I tried to disable PreSolve parameter and reduce the number of Threads but the issue remains the same. Knowing that I working on solving CVRP. For 16 customers and 8 vehicles, it works very well (58 s) but when I switch to 19 customers with 2 vehicles it takes more than 1000 s without returning a solution.

Edit
I changed these parameters:

    mdl.Params.Threads = 12
    mdl.Params.TimeLimit = 300
    mdl.Params.MIPGap = 0.05
    mdl.Params.MIPFocus=1
    mdl.Params.Presolve=2
    mdl.Params.PreSparsify=2
    mdl.Params.NoRelHeurTime=100
    mdl.Params.Heuristics=0.5
    mdl.Params.Method=0

Here is the log:

CPU model: Intel(R) Xeon(R) Platinum 8276 CPU @ 2.20GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 112 physical cores, 112 logical processors, using up to 12 threads

Optimize a model with 524310 rows, 684 columns and 40110732 nonzeros
Model fingerprint: 0xf11e235e
Variable types: 0 continuous, 684 integer (684 binary)
Coefficient statistics:
  Matrix range     [1e+00, 3e+01]
  Objective range  [3e-01, 5e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]
Found heuristic solution: objective 43.3769973
Presolve removed 0 rows and 0 columns (presolve time = 6s) ...
Presolve removed 0 rows and 0 columns (presolve time = 13s) ...
Presolve removed 0 rows and 0 columns (presolve time = 17s) ...
Presolve removed 0 rows and 0 columns (presolve time = 20s) ...
Presolve removed 0 rows and 0 columns (presolve time = 27s) ...
Presolve removed 0 rows and 0 columns (presolve time = 30s) ...
Presolve removed 0 rows and 0 columns (presolve time = 35s) ...
Presolve removed 0 rows and 0 columns (presolve time = 43s) ...
Presolve removed 0 rows and 0 columns (presolve time = 45s) ...
Presolve removed 0 rows and 0 columns (presolve time = 51s) ...
Presolve removed 0 rows and 0 columns (presolve time = 55s) ...
Presolve removed 0 rows and 0 columns (presolve time = 60s) ...
Presolve removed 0 rows and 0 columns (presolve time = 65s) ...
Presolve removed 0 rows and 0 columns (presolve time = 70s) ...
Presolve removed 0 rows and 0 columns (presolve time = 75s) ...
Presolve removed 0 rows and 0 columns (presolve time = 80s) ...
Presolve removed 0 rows and 0 columns (presolve time = 85s) ...
Presolve removed 0 rows and 0 columns (presolve time = 90s) ...
Presolve removed 0 rows and 0 columns (presolve time = 95s) ...
Presolve removed 0 rows and 0 columns (presolve time = 100s) ...
Presolve removed 0 rows and 0 columns (presolve time = 105s) ...
Presolve removed 0 rows and 0 columns (presolve time = 110s) ...
Presolve removed 0 rows and 0 columns (presolve time = 115s) ...
Presolve removed 0 rows and 0 columns (presolve time = 120s) ...
Presolve removed 0 rows and 0 columns (presolve time = 125s) ...
Presolve removed 0 rows and 0 columns (presolve time = 130s) ...
Presolve removed 0 rows and 0 columns (presolve time = 135s) ...
Presolve removed 0 rows and 0 columns (presolve time = 140s) ...
Presolve removed 0 rows and 0 columns (presolve time = 145s) ...
Presolve removed 0 rows and 0 columns (presolve time = 150s) ...
Presolve removed 0 rows and 0 columns (presolve time = 155s) ...
Presolve removed 0 rows and 0 columns (presolve time = 160s) ...
Presolve removed 0 rows and 0 columns (presolve time = 165s) ...
Presolve removed 0 rows and 0 columns (presolve time = 170s) ...
Presolve removed 0 rows and 0 columns (presolve time = 175s) ...
Presolve removed 0 rows and 0 columns (presolve time = 180s) ...
Presolve removed 0 rows and 0 columns (presolve time = 185s) ...
Presolve removed 0 rows and 0 columns (presolve time = 190s) ...
Presolve removed 0 rows and 0 columns (presolve time = 195s) ...
Presolve removed 0 rows and 0 columns (presolve time = 200s) ...
Presolve removed 0 rows and 0 columns (presolve time = 205s) ...
Presolve removed 0 rows and 0 columns (presolve time = 211s) ...
Presolve removed 0 rows and 0 columns (presolve time = 216s) ...
Presolve removed 0 rows and 0 columns (presolve time = 220s) ...
Presolve removed 0 rows and 0 columns (presolve time = 226s) ...
Presolve removed 0 rows and 0 columns (presolve time = 230s) ...
Presolve removed 0 rows and 0 columns (presolve time = 235s) ...
Presolve removed 0 rows and 0 columns (presolve time = 243s) ...
Presolve removed 0 rows and 0 columns (presolve time = 245s) ...
Presolve removed 0 rows and 0 columns (presolve time = 250s) ...
Presolve removed 0 rows and 0 columns (presolve time = 255s) ...
Presolve removed 0 rows and 0 columns (presolve time = 260s) ...
Presolve removed 0 rows and 0 columns (presolve time = 265s) ...
Presolve removed 0 rows and 0 columns (presolve time = 270s) ...
Presolve removed 0 rows and 0 columns (presolve time = 275s) ...
Presolve removed 0 rows and 0 columns (presolve time = 280s) ...
Presolve removed 0 rows and 0 columns (presolve time = 289s) ...
Presolve removed 0 rows and 0 columns (presolve time = 290s) ...
Presolve removed 0 rows and 0 columns (presolve time = 295s) ...
Presolve added 0 rows and 522620 columns
Presolve time: 297.21s

Explored 0 nodes (0 simplex iterations) in 300.47 seconds (168.69 work units)
Thread count was 1 (of 112 available processors)

Solution count 1: 43.377 

Time limit reached
Best objective 4.337699734045e+01, best bound -, gap -
No optimal solution found
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (linux64)

CPU model: Intel(R) Xeon(R) Platinum 8276 CPU @ 2.20GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 112 physical cores, 112 logical processors, using up to 12 threads

Optimize a model with 524310 rows, 684 columns and 40110732 nonzeros
Model fingerprint: 0xf11e235e
Variable types: 0 continuous, 684 integer (684 binary)
Coefficient statistics:
  Matrix range     [1e+00, 3e+01]
  Objective range  [3e-01, 5e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+02]


Presolve removed 0 rows and 0 columns (presolve time = 6s) ...
Presolve removed 0 rows and 0 columns (presolve time = 13s) ...
Presolve removed 0 rows and 0 columns (presolve time = 17s) ...
Presolve removed 0 rows and 0 columns (presolve time = 20s) ...
Presolve removed 0 rows and 0 columns (presolve time = 27s) ...
Presolve removed 0 rows and 0 columns (presolve time = 30s) ...
Presolve removed 0 rows and 0 columns (presolve time = 35s) ...
Presolve removed 0 rows and 0 columns (presolve time = 43s) ...
Presolve removed 0 rows and 0 columns (presolve time = 45s) ...
Presolve removed 0 rows and 0 columns (presolve time = 51s) ...
Presolve removed 0 rows and 0 columns (presolve time = 55s) ...
Presolve removed 0 rows and 0 columns (presolve time = 60s) ...
Presolve removed 0 rows and 0 columns (presolve time = 65s) ...
Presolve removed 0 rows and 0 columns (presolve time = 70s) ...
Presolve removed 0 rows and 0 columns (presolve time = 75s) ...
Presolve removed 0 rows and 0 columns (presolve time = 80s) ...
Presolve removed 0 rows and 0 columns (presolve time = 85s) ...
Presolve removed 0 rows and 0 columns (presolve time = 90s) ...
Presolve removed 0 rows and 0 columns (presolve time = 95s) ...
Presolve removed 0 rows and 0 columns (presolve time = 100s) ...
Presolve removed 0 rows and 0 columns (presolve time = 105s) ...
Presolve removed 0 rows and 0 columns (presolve time = 110s) ...
Presolve removed 0 rows and 0 columns (presolve time = 115s) ...
Presolve removed 0 rows and 0 columns (presolve time = 120s) ...
Presolve removed 0 rows and 0 columns (presolve time = 125s) ...
Presolve removed 0 rows and 0 columns (presolve time = 130s) ...
Presolve removed 0 rows and 0 columns (presolve time = 135s) ...
Presolve removed 0 rows and 0 columns (presolve time = 140s) ...
Presolve removed 0 rows and 0 columns (presolve time = 145s) ...
Presolve removed 0 rows and 0 columns (presolve time = 150s) ...
Presolve removed 0 rows and 0 columns (presolve time = 155s) ...
Presolve removed 0 rows and 0 columns (presolve time = 160s) ...
Presolve removed 0 rows and 0 columns (presolve time = 165s) ...
Presolve removed 0 rows and 0 columns (presolve time = 170s) ...
Presolve removed 0 rows and 0 columns (presolve time = 175s) ...
Presolve removed 0 rows and 0 columns (presolve time = 180s) ...
Presolve removed 0 rows and 0 columns (presolve time = 185s) ...
Presolve removed 0 rows and 0 columns (presolve time = 190s) ...
Presolve removed 0 rows and 0 columns (presolve time = 196s) ...
Presolve removed 0 rows and 0 columns (presolve time = 201s) ...
Presolve removed 0 rows and 0 columns (presolve time = 206s) ...
Presolve removed 0 rows and 0 columns (presolve time = 210s) ...
Presolve removed 0 rows and 0 columns (presolve time = 215s) ...
Presolve removed 0 rows and 0 columns (presolve time = 220s) ...
Presolve removed 0 rows and 0 columns (presolve time = 225s) ...
Presolve removed 0 rows and 0 columns (presolve time = 230s) ...
Presolve removed 0 rows and 0 columns (presolve time = 235s) ...
Presolve removed 0 rows and 0 columns (presolve time = 242s) ...
Presolve removed 0 rows and 0 columns (presolve time = 245s) ...
Presolve removed 0 rows and 0 columns (presolve time = 250s) ...
Presolve removed 0 rows and 0 columns (presolve time = 255s) ...
Presolve removed 0 rows and 0 columns (presolve time = 260s) ...
Presolve removed 0 rows and 0 columns (presolve time = 265s) ...
Presolve removed 0 rows and 0 columns (presolve time = 270s) ...
Presolve removed 0 rows and 0 columns (presolve time = 275s) ...
Presolve removed 0 rows and 0 columns (presolve time = 289s) ...
Presolve removed 0 rows and 0 columns (presolve time = 290s) ...
Presolve removed 0 rows and 0 columns (presolve time = 295s) ...
Presolve removed 0 rows and 0 columns (presolve time = 300s) ...
Presolve added 0 rows and 522620 columns
Presolve time: 300.22s

Explored 0 nodes (0 simplex iterations) in 300.68 seconds (168.33 work units)
Thread count was 1 (of 112 available processors)

Solution count 1: 43.377 

Time limit reached
Best objective 4.337699734045e+01, best bound -, gap -
No optimal solution found
run time average CVRP:  300.798810005188
IIS computation: initial model status unknown, solving to determine model status
Found heuristic solution: objective 0.0000000

Explored 0 nodes (0 simplex iterations) in 3.13 seconds (0.78 work units)
Thread count was 1 (of 112 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 5.00e-02)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
IIS runtime: 3.24 seconds (0.78 work units)
$\endgroup$
10
  • 1
    $\begingroup$ "it takes more than 1000 s without returning a solution" There are quite a few solutions. (lines with H, indicating a heuristic solution). Just use a time limit (or other limit) and retrieve the best. $\endgroup$ Commented Dec 7, 2023 at 16:02
  • $\begingroup$ The log only shows about 70 seconds of presolve time. The vast majority of the time is spent banging on the root node. $\endgroup$
    – prubin
    Commented Dec 7, 2023 at 16:49
  • $\begingroup$ Thank you for you answers. It takes 70s without removing anything and after presolve phase, the number of nonzeros increases. Basically, the presolve phase consists in reducing the model in terms of rows and columns $\endgroup$
    – MAYA
    Commented Dec 7, 2023 at 16:56
  • 1
    $\begingroup$ @MAYA what formulation are you using for the CVRP. Although the CVRP is a notoriously difficult problem to solve, it seems a little extreme that it takes so much time for such a small problem. Could you share you model and maybe event the data? $\endgroup$
    – Sune
    Commented Dec 8, 2023 at 10:21
  • 2
    $\begingroup$ 19 customers and 2 vehicles, and the model has 524310 constraints. That looks odd $\endgroup$
    – fontanf
    Commented Dec 8, 2023 at 11:02

2 Answers 2

1
$\begingroup$

In the log you show, the Presolve parameter was changed to 2. That value corresponds to an aggressive setting. It can therefore be expected that presolve takes longer than when left at the default value. Note that this setting doesn't guarantee that presolve will find more changes to do. It will try harder, but may not succeed...

If presolve, whether using values 1 or 2, doesn't make the problem easier, you can remove it by using the value 0.

$\endgroup$
4
$\begingroup$

It is a general misconception that presolve reduces the size of the problem. While this is a typical side effect, the actual goal of the presolving step is to find an equivalent model that is more amendable to the techniques available to the solver.

For example, this includes reformulating indicator constraints to big-M to strengthen the dual bound of the LP relaxation. Indicator constraints would otherwise just be ignored by the LP solver.

Your model instance is a pretty extreme example, and you could try playing with the Presolve and other presolving parameters to see whether you can save some time there. It appears as if Gurobi spends time on (expensive) presolving routines that do not lead to a better or smaller model.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I tried changing the value of Presolve but it does not change anything. I tried to change other parameters as MIPGap and PreSparsify but I got the same thing. $\endgroup$
    – MAYA
    Commented Dec 8, 2023 at 10:21
  • $\begingroup$ If you want to disable presolve, you can set Presolve=0. This should at least save some time and the root node solving and branch-and-bound process can begin sooner. $\endgroup$
    – mattmilten
    Commented Dec 8, 2023 at 10:27

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.