Gurobi spend more time in presolve in small model

Question

I have small model to optimze in Gurobi. The problem that it takes a lot of time in presolving without removing any rows or variables. I tried to disable PreSolve paramter 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 solution. Here is the log:

Set parameter Threads to value 56
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 56 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 = 25s) ...
Presolve removed 0 rows and 0 columns (presolve time = 32s) ...
Presolve removed 0 rows and 0 columns (presolve time = 35s) ...
Presolve removed 0 rows and 0 columns (presolve time = 40s) ...
Presolve removed 0 rows and 0 columns (presolve time = 45s) ...
Presolve removed 0 rows and 0 columns (presolve time = 50s) ...
Presolve removed 0 rows and 0 columns (presolve time = 55s) ...
Presolve removed 0 rows and 0 columns (presolve time = 64s) ...
Presolve removed 0 rows and 0 columns (presolve time = 70s) ...
Presolve time: 69.83s
Presolved: 524310 rows, 684 columns, 40110694 nonzeros
Variable types: 0 continuous, 684 integer (684 binary)
Root relaxation presolved: 684 rows, 524994 columns, 40111378 nonzeros


Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -0.0000000e+00   0.000000e+00   5.700000e+01    115s
      41    1.4942544e+01   0.000000e+00   0.000000e+00    115s
      41    1.4942544e+01   0.000000e+00   2.000000e-06    115s

Use crossover to convert LP symmetric solution to basic solution...

Root crossover log...

       1 DPushes remaining with DInf 0.0000000e+00               117s
       0 DPushes remaining with DInf 0.0000000e+00               117s

      27 PPushes remaining with PInf 0.0000000e+00               117s
       0 PPushes remaining with PInf 0.0000000e+00               117s

  Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00    117s


Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
      72    1.4942544e+01   0.000000e+00   0.000000e+00    117s
      72    1.4942544e+01   0.000000e+00   0.000000e+00    119s
      72    1.4942544e+01   0.000000e+00   0.000000e+00    121s

Root relaxation: objective 1.494254e+01, 72 iterations, 46.50 seconds (39.46 work units)

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

     0     0   14.94254    0   40   43.37700   14.94254  65.6%     -  127s
H    0     0                      41.2306564   14.94254  63.8%     -  135s
     0     0   16.53206    0   32   41.23066   16.53206  59.9%     -  161s
     0     0   16.53206    0   32   41.23066   16.53206  59.9%     -  203s
H    0     0                      37.7572196   16.53206  56.2%     -  217s
     0     0   16.53206    0   32   37.75722   16.53206  56.2%     -  245s
     0     0   16.53206    0   40   37.75722   16.53206  56.2%     -  276s
     0     0   16.53206    0   32   37.75722   16.53206  56.2%     -  305s
H    0     0                      37.4178668   16.53206  55.8%     -  320s
     0     0   16.53206    0   32   37.41787   16.53206  55.8%     -  325s
     0     0   16.53206    0   32   37.41787   16.53206  55.8%     -  352s
     0     0   16.54588    0   50   37.41787   16.54588  55.8%     -  388s
H    0     0                      37.1018717   16.54588  55.4%     -  397s
H    0     0                      34.1244024   16.54588  51.5%     -  400s
     0     0   16.56291    0   57   34.12440   16.56291  51.5%     -  409s
     0     0   16.56934    0   58   34.12440   16.56934  51.4%     -  421s
     0     0   16.62160    0   64   34.12440   16.62160  51.3%     -  444s
     0     0   16.62160    0   64   34.12440   16.62160  51.3%     -  465s
     0     0   16.62160    0   56   34.12440   16.62160  51.3%     -  489s
     0     0   16.64008    0   50   34.12440   16.64008  51.2%     -  529s
     0     0   16.64405    0   56   34.12440   16.64405  51.2%     -  555s
     0     0   16.64405    0   57   34.12440   16.64405  51.2%     -  573s
     0     0   16.65711    0   65   34.12440   16.65711  51.2%     -  597s
H    0     0                      31.7808513   16.65711  47.6%     -  614s
     0     0   16.66624    0   56   31.78085   16.66624  47.6%     -  624s
     0     0   16.66624    0   56   31.78085   16.66624  47.6%     -  635s
     0     0   16.66624    0   47   31.78085   16.66624  47.6%     -  668s
     0     0   16.66624    0   49   31.78085   16.66624  47.6%     -  691s
     0     0   16.69817    0   46   31.78085   16.69817  47.5%     -  705s
H    0     0                      31.3353414   16.69817  46.7%     -  720s
     0     0   16.69817    0   50   31.33534   16.69817  46.7%     -  732s
     0     0   16.70180    0   57   31.33534   16.70180  46.7%     -  760s
H    0     0                      26.8624304   16.70180  37.8%     -  771s
H    0     0                      24.6815680   16.70180  32.3%     -  778s
     0     0   16.70180    0   57   24.68157   16.70180  32.3%     -  784s
     0     0   16.70180    0   56   24.68157   16.70180  32.3%     -  801s
     0     0   16.70180    0   56   24.68157   16.70180  32.3%     -  824s
     0     0   16.70180    0   49   24.68157   16.70180  32.3%     -  863s

Thank you for your help.

Answer 1

Presolve is just overwhelmed with the amount of information and can't simplify so much at once.

Disabling the PreSolve parameter and reducing the number of threads did not have any impact on the solving time, suggesting that the issue is not related to these parameters.

One possible reason for the slow solving time could be the complexity of the problem itself. CVRP (Capacitated Vehicle Routing Problem) is a well-known NP-hard problem, meaning that it is computationally challenging to solve optimally for large instances. The number of customers and vehicles in your problem also affects the solving time. As you mentioned, the solving time is significantly longer when there are 19 customers with only 2 vehicles compared to 16 customers with 8 vehicles.

Answer 2

Here's an alternative approach to analyzing the data using pandas:

import pandas as pd

# Assuming the data is stored in a text file named 'data.txt'
with open('data.txt', 'r') as file:
    data = file.readlines()

# Filter out lines with headers and H states
filtered_data = [line for line in data if line.strip() and line[0] not in ['H', '#']]

# Split each line into a list and convert it into a dictionary
data_dicts = [dict(zip(['M1', 'M2', 'M3', 'N1', 'N2', 'E1', 'E2', 'E3', 'M/N', 'E/N', 'R1', 'R2', 'T'], line.split())) for line in filtered_data]

# Convert the list of dictionaries into a DataFrame
df = pd.DataFrame(data_dicts)

# Now we can perform analysis on the DataFrame

# Example: Identify the time when E/N reached a maximum value
max_E_N_time = df[df['E/N'] == df['E/N'].max()]['T'].values[0]

print(f"The time when E/N reached its maximum value is {max_E_N_time}s.")