Small model that takes more time
Answered
Hi!
I'm working on solving the capacited vehicle routing problem with Gurobi. The problem that the model is small (684 binary variables) and takes more time. I set the threads to 56 (which is the maximum) but it doesn't chaneg the running time. Morover, the model takes 356s for the first time but when I run it for the second time, it takes more than 900 seconds.
Here is the output of gurobi:
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 support and your help.
Assia
-
Hi Assia,
As explained in Does using more threads make Gurobi faster? using more threads does not always speed up solve times. In your log we can see that the Gurobi spends all the time in the root node, in this case, adding threads will not help as there is little parallelization possible. Moreover, more threads can actually be bad in this case (as you observed) because they may waste time synchronizing.
What kind of solving times are you looking for? I would say ~300 sec is quite quick given that even if your model doesn't have many variables, it does have many constraints and especially many non-zeros, which also account for model size.
Given the large number of nonzeros, you may want to try setting the parameter PreSparsify to 1 or 2. Also, since presolve doesn't seem to remove anything from your model with default settings, you may want to try Presolve=2 for more agressive presolve.
Best regards,
Elisabeth
0 -
Hi,
I tried this parameters but still got the same issue. I'm working with 1400 GB of memory and I reduce the number of threads with Presolve set to 2. I'm comparing with the paper below where they run the same model with the same dataset in 9,09 seconds. They run it on a PC with Intel Xeon 32 cores, 256 GB RAM, which is less to the size of memory in my case:
https://hrcak.srce.hr/file/285563
What I can not understand is why the solver takes more time in presolving and then it removes 0 rows and 0 columns.
Thank you,
Assia
0 -
Hi,
I tried various parameters including disabling Presolve but the model takes more than 1000 s. What I can not understand in the log is that whay the number of nonzeros increase.
Thank you for your support.
Assia
0 -
Hi,
Thank you, it is related to my post. I changed other parameters such as MIPGaP and PreSparsify. Still the presolve spend time without enhancing the solution. The model is small regarding others models and the Presolve phase takes more time. Disabling the Presolve phase does not change anything. Thank you for your help.
Set parameter Threads to value 12 Set parameter TimeLimit to value 300 Set parameter MIPGap to value 0.05 Set parameter MIPFocus to value 1 Set parameter Presolve to value 2 Set parameter PreSparsify to value 2 Set parameter NoRelHeurTime to value 100 Set parameter Heuristics to value 0.5 Set parameter Method to value 0 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] 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)
0 -
Hi Assia,
Elisabeth is on holiday at the moment but I can have a look. Could you upload a model file somewhere I can access it, such as Google Drive, Dropbox or Github?
- Riley
0 -
Hi Riley,
Thank you. I really appreciated it. Here is the link:
https://drive.google.com/file/d/1GJnfCC3Sef7PIyrapso3DjOcEhvq0wWl/view?usp=sharing
For data: https://drive.google.com/file/d/1ggRah3npRyejiLUvoMAbAIm7az8CNXmX/view?usp=drive_link
Please let me know if you it is ok for the acces.
Best regards,
Assia
0 -
Hi Assia,
It is probably easier if you share a model file, instead of your code.
- Export your models as MPS. To export the model file, use the write() function of your chosen API.
- Compress the model file using a compression tool like bzip2, zip, 7zip, or gzip.
- Upload to Google Drive and set access to "Anyone with the link"
- Riley
0 -
Hi Riley,
Thank you. I've just finished to upload the zip to Google Drive. Here is the link:
https://drive.google.com/file/d/1sN2f3QfLpuFkjwrBT9knYejXJRosgxp2/view?usp=sharing
Thank you.
Assia
0 -
Hi Assia,
Disabling the Presolve phase does not change anything
I cannot reproduce this observation:
Set parameter Presolve to value 0
Using license file /Users/riley.clement/gurobi.lic
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (mac64[x86])
Copyright (c) 2023, Gurobi Optimization, LLC
Read MPS format model from file modelcvrp.mps
Reading time = 6.14 seconds
CVRP3: 524310 rows, 684 columns, 40110732 nonzeros
CPU model: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
Thread count: 4 physical cores, 8 logical processors, using up to 8 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 = 8s) ...
Variable types: 0 continuous, 684 integer (684 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 5.100000e+01 0.000000e+00 15s
65 1.4942544e+01 0.000000e+00 0.000000e+00 17s
...What I can not understand in the log is that why the number of nonzeros increase.
From your own logs we can see this is not true :
Optimize a model with 524310 rows, 684 columns and 40110732 nonzeros
...
Presolved: 524310 rows, 684 columns, 40110694 nonzerosThe logs then show the following:
Root relaxation presolved: 684 rows, 524994 columns, 40111378 nonzeros
so my guess is that this is indicating that the dual LP is created, and slack variables are added. Note 524310 + 684 = 524994, and 40110694 + 684 = 40111378.
I'm comparing with the paper below where they run the same model with the same dataset in 9,09 seconds. They run it on a PC with Intel Xeon 32 cores, 256 GB RAM, which is less to the size of memory in my case
Also, importantly, they are using Gurobi v6.5, and you are using Gurobi v10.0.3 which is much faster. I also come nowhere near being able to produce the result of 9.09s on a machine superior to theirs. By far, the most likely explanation is that the model you are solving is simply not the same - either an incorrect implementation, or different data. This is further supported by the fact your optimal value is somewhere between 24.68157 16.70180, based off your first log, but they are reporting optimal values of at least 200 in their table.
- Riley
0 -
Hi Riley,
Thank you for these insightful explanations. Now, I understand why the nonzero variables increases.
For the paper, I working on minimizing time rather than distance (Time = Distance * Speed). However, I tried to reproduce the same model with distance. For the first instance, it is ok/ I got the same result and even the same runtime (235s). But for the second instance (19 customers with 2 trucks). The same problem, it takes a lot of time to achieve the best solution which is 212. Here is the log, I tried to set some parameters including disabling PreSolve to speed up the model. Any suggestions please that can I help me:Set parameter Presolve to value 0 Set parameter PrePasses to value 5 Set parameter Heuristics to value 0.005 Set parameter PreSparsify to value 0 Set parameter Cuts to value 1 Set parameter MIPFocus to value 3 Set parameter Threads to value 1 Set parameter NodefileStart to value 0.5 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 1 threads Optimize a model with 524310 rows, 684 columns and 40110732 nonzeros Model fingerprint: 0xbf1c0f3c Variable types: 0 continuous, 684 integer (684 binary) Coefficient statistics: Matrix range [1e+00, 3e+01] Objective range [4e+00, 5e+01] Bounds range [1e+00, 1e+00] RHS range [1e+00, 2e+02] Presolve removed 0 rows and 0 columns (presolve time = 7s) ... Variable types: 0 continuous, 684 integer (684 binary) Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 0.0000000e+00 5.100000e+01 0.000000e+00 16s 65 1.6699788e+02 0.000000e+00 0.000000e+00 17s Root relaxation: objective 1.669979e+02, 65 iterations, 7.49 seconds (1.67 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 166.99788 0 40 - 166.99788 - - 21s 0 0 177.87570 0 46 - 177.87570 - - 50s 0 0 184.76234 0 32 - 184.76234 - - 73s 0 0 184.76234 0 39 - 184.76234 - - 94s 0 0 184.76234 0 32 - 184.76234 - - 123s 0 0 184.76234 0 32 - 184.76234 - - 135s 0 0 184.76234 0 32 - 184.76234 - - 159s 0 0 184.76234 0 32 - 184.76234 - - 171s 0 0 184.86500 0 54 - 184.86500 - - 191s 0 0 185.00278 0 53 - 185.00278 - - 206s 0 0 185.00278 0 66 - 185.00278 - - 230s 0 0 185.00278 0 59 - 185.00278 - - 245s 0 0 185.00916 0 60 - 185.00916 - - 285s 0 0 185.02709 0 60 - 185.02709 - - 302s 0 0 185.06071 0 63 - 185.06071 - - 314s 0 0 185.29184 0 61 - 185.29184 - - 329s 0 0 185.29184 0 50 - 185.29184 - - 358s 0 2 185.55564 0 50 - 185.55564 - - 429s 1 3 187.27480 1 50 - 185.55564 - 61.0 439s 2 4 185.55564 1 54 - 185.55564 - 31.0 444s 3 5 185.55564 2 68 - 185.55564 - 26.0 459s 4 6 185.55564 3 58 - 185.55564 - 19.8 470s 5 7 185.55564 4 53 - 185.55564 - 16.4 485s 6 8 185.55564 5 49 - 185.55564 - 13.8 496s 7 9 187.53938 6 44 - 185.68158 - 15.3 510s 8 10 185.75938 6 50 - 185.71349 - 14.2 524s 9 11 191.62076 5 41 - 185.75938 - 16.4 539s 10 12 187.84746 7 48 - 186.08231 - 16.8 553s 11 13 186.10956 7 42 - 186.10956 - 15.5 564s 12 14 186.72450 8 37 - 186.72450 - 14.9 578s 13 15 190.23611 9 30 - 186.72450 - 15.3 592s 14 16 187.04729 9 36 - 186.74033 - 14.7 607s 15 17 190.23611 8 31 - 187.09667 - 15.5 621s 16 18 187.32133 2 58 - 187.32133 - 16.0 636s 17 19 188.66090 2 47 - 187.33019 - 16.2 647s 18 20 188.62600 3 51 - 187.36047 - 16.7 658s 19 21 189.25729 3 44 - 187.36047 - 17.8 673s 20 22 189.53183 4 49 - 187.59707 - 19.1 685s 21 23 188.73765 2 48 - 187.60233 - 19.1 699s 22 24 187.94971 7 45 - 187.91729 - 18.6 710s 23 25 188.73765 3 47 - 187.98940 - 18.6 724s 24 26 187.98940 8 51 - 187.98940 - 17.8 735s 25 27 187.98940 9 52 - 187.98940 - 17.2 745s 26 28 188.51257 10 42 - 188.05663 - 16.8 759s 27 29 189.11880 10 38 - 188.08631 - 17.4 772s 28 30 188.08631 8 43 - 188.08631 - 16.9 783s 29 31 188.40504 9 39 - 188.24238 - 16.4 796s 30 32 193.94666 9 34 - 188.40504 - 17.2 810s 31 33 192.77457 9 37 - 188.41013 - 17.4 823s 32 34 188.53254 8 30 - 188.53254 - 17.1 836s 33 35 192.48031 8 40 - 188.57882 - 17.2 849s 34 36 188.57882 11 40 - 188.57882 - 16.8 862s 35 37 188.73338 12 36 - 188.64850 - 16.4 875s 36 38 190.49009 4 44 - 188.66090 - 16.6 887s0 -
Hi Assia,
My first suggestion would be to run this model several times (perhaps 10?) with different values of Seed to get an understanding of the performance variability.
Is there any reason you are limiting Threads to 1? I would let the threads parameter take its default value unless you are encountering memory errors, otherwise you are handcuffing the solver's abilities.
Also keep in mind that if all that changes between these two models is the objective function then any feasible solution for one, is a feasible solution for the other, and you can use it to warm start by either using MST files, or by simply terminating the first model, changing the objective function, and resuming by calling optimize() again.
- Riley
0 -
When I start to solve the file from https://drive.google.com/file/d/1sN2f3QfLpuFkjwrBT9knYejXJRosgxp2/view?usp=sharing, I get a different model fingerprint: 0xf11e235e vs 0xbf1c0f3c in your log. This shows that the model is not exactly the same, and it's therefore difficult to draw any conclusion.
You may want to do your experiments from the generated MPS file, with a command such as this one:
gurobi_cl presolve=0 prepasses=5 heuristics=0.005 presparsify=0 cuts=1 mipfocus=3 threads=1 nodefilestart=0.5 model.mps
0 -
Hi,
Thank you for your reply. The model fingerprint is 0xf11e235e as showed in my first post. While 0xbf1c0f3c is the model with minimizing distance rather than time. Here is the ongoing solving with your suggested paramter:
Set parameter Presolve to value 0 Set parameter Threads to value 1 Set parameter PrePasses to value 5 Set parameter NodefileStart to value 0.5 Set parameter MIPFocus to value 3 Set parameter PreSparsify to value 0 Set parameter Cuts to value 1 Set parameter Heuristics to value 0.005 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 1 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 = 7s) ... Variable types: 0 continuous, 684 integer (684 binary) Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 0.0000000e+00 5.100000e+01 0.000000e+00 16s 65 1.4942544e+01 0.000000e+00 0.000000e+00 17s Root relaxation: objective 1.494254e+01, 65 iterations, 7.41 seconds (1.67 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 - 14.94254 - - 21s 0 0 15.91586 0 48 - 15.91586 - - 50s 0 0 16.53206 0 32 - 16.53206 - - 80s 0 0 16.53206 0 32 - 16.53206 - - 94s 0 0 16.53206 0 32 - 16.53206 - - 113s 0 0 16.53206 0 32 - 16.53206 - - 142s 0 0 16.53206 0 32 - 16.53206 - - 153s 0 0 16.53206 0 32 - 16.53206 - - 166s 0 0 16.57062 0 40 - 16.57062 - - 193s 0 0 16.57062 0 44 - 16.57062 - - 207s 0 0 16.59059 0 51 - 16.59059 - - 217s 0 0 16.59059 0 64 - 16.59059 - - 259s 0 0 16.59059 0 66 - 16.59059 - - 270s 0 0 16.59280 0 55 - 16.59280 - - 293s 0 0 16.59280 0 63 - 16.59280 - - 311s 0 0 16.59280 0 64 - 16.59280 - - 328s0 -
When I kept default value of the parameters Heuristics, Cuts, PreSparsify and NodefileStart. there is a heuristic solution to start:
Set parameter Presolve to value 0 Set parameter Threads to value 1 Set parameter PrePasses to value 5 Set parameter MIPGap to value 0.05 Set parameter MIPFocus to value 3 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 1 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 = 7s) ... Variable types: 0 continuous, 684 integer (684 binary) Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 0.0000000e+00 5.100000e+01 0.000000e+00 18s 65 1.4942544e+01 0.000000e+00 0.000000e+00 19s Root relaxation: objective 1.494254e+01, 65 iterations, 7.41 seconds (1.67 work units) Total elapsed time = 35.12s 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% - 38s H 0 0 41.7778623 14.94254 64.2% - 45s 0 0 16.53206 0 32 41.77786 16.53206 60.4% - 74s 0 0 16.53206 0 32 41.77786 16.53206 60.4% - 122s H 0 0 37.8298677 16.53206 56.3% - 131s H 0 0 33.9996130 16.53206 51.4% - 133s 0 0 16.70560 0 52 33.99961 16.70560 50.9% - 209s H 0 0 33.4926672 16.70560 50.1% - 220s 0 0 16.70560 0 60 33.49267 16.70560 50.1% - 229s 0 0 16.76211 0 32 33.49267 16.76211 50.0% - 303s0 -
Hi Assia,
Just a reminder that there are certain abilities of the solver which are not enabled when you use one thread. I would experiment with letting Threads take its default value.
- Riley
0 -
Hi Riley,
Thank you for your reply. If understand from the response below that more Threads make Gurobi spends more time. The machine has 112 Threads. Would you please tell me how many threads I have to set?
As explained in Does using more threads make Gurobi faster? using more threads does not always speed up solve times. In your log we can see that the Gurobi spends all the time in the root node, in this case, adding threads will not help as there is little parallelization possible. Moreover, more threads can actually be bad in this case (as you observed) because they may waste time synchronizing.
0 -
I would try Threads=4, and also simply not setting this parameter and letting it take it's default.
0 -
Hi Assia,
I agree with Riley, my original comment
As explained in Does using more threads make Gurobi faster? using more threads does not always speed up solve times. In your log we can see that the Gurobi spends all the time in the root node, in this case, adding threads will not help as there is little parallelization possible. Moreover, more threads can actually be bad in this case (as you observed) because they may waste time synchronizing.
was referring to your initial setting of 56 threads. Increasing the number of threads typically doesn't help beyond a certain point, but Threads=1 can definitely limit the solver's capabilities. I would experiment setting Threads=0 (which is the default) or 4, 8, 16... and make a decision after testing, as it is difficult to know which setting is the best without testing.
Elisabeth
0 -
Hi Elisabeth,
Thank you for this explanation. By setting Threads to 0, it takes more than 8812s to get the optimal result. However, the optimal result can be retrieved in the following line with 19.0279979 as a value of the objective function in 692s. I don't understand why it didn't stop. It is a minimizing problem.
H 124 128 19.0279979 16.62000 12.7% 17.0 692s
Set parameter Presolve to value 0 Set parameter MIPGap to value 0.05 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 32 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 = 7s) ... Variable types: 0 continuous, 684 integer (684 binary) Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 0.0000000e+00 5.100000e+01 0.000000e+00 18s 65 1.4942544e+01 0.000000e+00 0.000000e+00 19s Root relaxation: objective 1.494254e+01, 65 iterations, 7.40 seconds (1.67 work units) Total elapsed time = 20.90s 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% - 23s H 0 0 41.7778623 14.94254 64.2% - 26s 0 0 15.91586 0 47 41.77786 15.91586 61.9% - 51s 0 0 16.53206 0 32 41.77786 16.53206 60.4% - 99s H 0 0 40.8194903 16.53206 59.5% - 112s 0 0 16.53206 0 32 40.81949 16.53206 59.5% - 121s H 0 0 39.8428479 16.53206 58.5% - 136s 0 0 16.53206 0 32 39.84285 16.53206 58.5% - 157s H 0 0 39.7006710 16.53206 58.4% - 167s H 0 0 38.3516076 16.53206 56.9% - 169s 0 0 16.53206 0 32 38.35161 16.53206 56.9% - 200s 0 0 16.53206 0 32 38.35161 16.53206 56.9% - 221s 0 0 16.53206 0 32 38.35161 16.53206 56.9% - 241s H 0 0 22.7663062 16.53206 27.4% - 250s 0 0 16.57062 0 40 22.76631 16.57062 27.2% - 272s 0 0 16.57062 0 40 22.76631 16.57062 27.2% - 290s 0 0 16.59059 0 48 22.76631 16.59059 27.1% - 308s 0 0 16.59597 0 56 22.76631 16.59597 27.1% - 337s 0 0 16.59597 0 57 22.76631 16.59597 27.1% - 354s 0 0 16.59597 0 63 22.76631 16.59597 27.1% - 385s 0 0 16.59656 0 65 22.76631 16.59656 27.1% - 399s 0 0 16.59656 0 71 22.76631 16.59656 27.1% - 419s 0 0 16.59656 0 59 22.76631 16.59656 27.1% - 461s 0 2 16.59714 0 59 22.76631 16.59714 27.1% - 519s 1 4 16.59714 1 63 22.76631 16.59714 27.1% 7.0 535s 3 8 16.60002 2 68 22.76631 16.60002 27.1% 15.7 553s 7 16 16.60002 3 70 22.76631 16.60002 27.1% 18.3 572s 15 32 16.62000 4 67 22.76631 16.62000 27.0% 20.1 592s H 31 64 22.6003461 16.62000 26.5% 20.4 635s H 33 64 21.1157499 16.62000 21.3% 19.4 635s 63 96 16.62383 6 60 21.11575 16.62000 21.3% 19.5 645s 95 128 16.67433 7 52 21.11575 16.62000 21.3% 17.1 692s H 103 128 21.1076027 16.62000 21.3% 16.5 692s H 108 128 20.9938606 16.62000 20.8% 17.0 692s H 118 128 20.7987134 16.62000 20.1% 17.0 692s H 124 128 19.0279979 16.62000 12.7% 17.0 692s 127 151 16.98199 7 36 19.02800 16.62000 12.7% 17.0 701s 159 173 17.59808 8 26 19.02800 16.62000 12.7% 15.6 712s 191 199 16.98199 8 38 19.02800 16.62000 12.7% 14.9 736s 223 235 16.99363 9 36 19.02800 16.62000 12.7% 14.3 745s 272 262 17.00861 11 37 19.02800 16.62000 12.7% 13.9 755s 324 272 17.17889 13 29 19.02800 16.62000 12.7% 13.4 769s 375 281 17.18232 14 35 19.02800 16.62000 12.7% 12.9 1182s 413 305 17.40593 15 23 19.02800 16.62000 12.7% 13.0 1199s 474 327 17.54837 16 25 19.02800 16.62000 12.7% 12.6 1216s 526 350 18.19719 16 20 19.02800 16.62000 12.7% 12.5 1234s 609 362 18.71662 17 22 19.02800 16.62000 12.7% 12.0 1249s 663 382 infeasible 18 19.02800 16.62128 12.6% 11.9 1283s 724 404 16.63976 7 49 19.02800 16.63976 12.6% 11.8 1301s 793 447 16.73732 9 47 19.02800 16.65033 12.5% 11.6 1319s 875 486 16.86217 12 28 19.02800 16.65033 12.5% 11.6 1339s 969 514 17.11761 16 22 19.02800 16.65033 12.5% 11.5 1361s 1038 542 17.13672 18 24 19.02800 16.65033 12.5% 11.3 1383s 1120 591 17.31859 20 35 19.02800 16.65033 12.5% 11.3 1399s 1227 616 18.11314 24 23 19.02800 16.65033 12.5% 11.3 1424s 1293 678 18.16896 25 27 19.02800 16.65033 12.5% 11.3 1444s 1398 710 18.33216 27 24 19.02800 16.65033 12.5% 11.4 1465s 1521 760 infeasible 31 19.02800 16.65033 12.5% 11.3 1486s 1627 815 infeasible 30 19.02800 16.65033 12.5% 11.4 1505s 1720 849 18.97280 31 18 19.02800 16.69360 12.3% 11.5 1530s 1860 918 16.98199 8 40 19.02800 16.69360 12.3% 11.4 1548s 1991 953 17.38269 13 47 19.02800 16.69360 12.3% 11.4 1583s 2109 1030 17.48618 17 50 19.02800 16.69360 12.3% 11.4 1609s 2270 1088 17.53908 22 53 19.02800 16.69360 12.3% 11.3 1630s 2422 1152 18.14700 28 34 19.02800 16.69360 12.3% 11.3 1649s 2556 1228 18.42768 32 25 19.02800 16.69360 12.3% 11.3 1673s 2722 1277 infeasible 36 19.02800 16.69360 12.3% 11.3 1700s 2879 1327 infeasible 35 19.02800 16.82822 11.6% 11.2 1729s 3011 1383 16.98226 10 32 19.02800 16.82822 11.6% 11.4 1758s 3165 1466 17.76924 19 33 19.02800 16.82822 11.6% 11.4 1783s 3341 1517 18.25665 25 35 19.02800 16.82822 11.6% 11.5 1811s 3529 1595 18.74826 13 43 19.02800 16.88819 11.2% 11.5 1841s 3741 1637 18.04249 14 36 19.02800 16.88819 11.2% 11.4 1871s 3947 1714 18.27279 18 42 19.02800 16.88819 11.2% 11.4 1909s 4142 1796 infeasible 24 19.02800 16.88819 11.2% 11.5 1936s 4360 1865 18.80571 22 24 19.02800 16.98799 10.7% 11.5 1967s 4562 1926 18.17777 13 48 19.02800 16.98799 10.7% 11.6 1999s 4828 2029 18.54028 20 31 19.02800 16.98799 10.7% 11.5 2031s 5119 2092 infeasible 31 19.02800 17.01022 10.6% 11.5 2070s 5355 2150 17.59742 20 14 19.02800 17.13322 10.0% 11.6 2107s 5620 2253 17.83315 24 35 19.02800 17.13322 10.0% 11.6 2145s 5924 2322 cutoff 29 19.02800 17.28009 9.19% 11.6 2185s 6222 2419 17.93487 18 22 19.02800 17.30747 9.04% 11.6 2224s 6519 2518 18.29362 26 34 19.02800 17.30747 9.04% 11.6 2257s 6825 2519 18.55876 19 59 19.02800 17.30747 9.04% 11.7 2368s 6827 2520 17.69749 8 40 19.02800 17.30747 9.04% 11.7 2427s 6828 2521 17.57622 11 32 19.02800 17.30747 9.04% 11.7 2508s 6829 2522 18.26644 18 32 19.02800 17.30747 9.04% 11.7 2605s 6830 2522 18.29439 33 61 19.02800 17.30747 9.04% 11.7 2744s 6831 2523 17.71208 26 51 19.02800 17.30747 9.04% 11.7 2797s 6832 2524 18.52152 24 62 19.02800 17.30747 9.04% 11.7 2809s 6833 2524 18.16224 29 65 19.02800 17.30747 9.04% 11.7 2844s 6834 2525 18.91501 13 64 19.02800 17.30747 9.04% 11.7 2914s 6835 2526 18.45099 15 56 19.02800 17.30747 9.04% 11.7 2930s 6836 2526 17.98569 21 66 19.02800 17.30747 9.04% 11.7 2974s 6837 2527 18.25769 18 71 19.02800 17.30747 9.04% 11.7 3033s 6838 2528 17.59078 11 73 19.02800 17.30747 9.04% 11.7 3100s 6839 2528 18.13961 19 71 19.02800 17.30747 9.04% 11.7 3197s 6840 2529 17.90095 20 76 19.02800 17.30747 9.04% 11.7 3239s 6841 2530 18.29030 16 83 19.02800 17.30747 9.04% 11.7 3315s 6842 2530 17.78707 17 86 19.02800 17.30747 9.04% 11.7 3329s 6843 2531 18.60921 18 89 19.02800 17.30747 9.04% 11.7 3343s 6844 2532 18.24148 20 90 19.02800 17.30747 9.04% 11.7 3356s 6845 2532 18.24703 13 92 19.02800 17.30747 9.04% 11.7 3393s 6846 2533 17.49491 13 93 19.02800 17.30747 9.04% 11.7 3469s 6847 2534 18.47385 15 94 19.02800 17.30747 9.04% 11.7 3483s 6848 2534 18.28502 18 95 19.02800 17.30747 9.04% 11.7 3525s 6849 2535 17.93162 10 76 19.02800 17.30747 9.04% 11.7 3618s 6850 2536 18.61296 23 88 19.02800 17.30747 9.04% 11.7 3679s 6851 2536 17.63279 20 91 19.02800 17.30747 9.04% 11.7 3763s 6852 2537 18.92914 10 88 19.02800 17.30747 9.04% 11.7 3776s 6853 2538 17.91369 19 101 19.02800 17.30747 9.04% 11.7 3828s 6854 2538 17.86761 21 88 19.02800 17.30747 9.04% 11.7 3903s 6855 2539 18.39016 26 90 19.02800 17.30747 9.04% 11.7 3958s 6856 2540 17.97186 22 98 19.02800 17.30747 9.04% 11.7 4050s 6857 2540 18.18034 16 94 19.02800 17.30747 9.04% 11.7 4106s 6858 2541 18.29257 17 98 19.02800 17.30747 9.04% 11.7 4195s 6859 2542 18.91096 14 99 19.02800 17.30747 9.04% 11.7 4217s 6860 2542 18.57762 33 100 19.02800 17.30747 9.04% 11.6 4267s 6861 2543 18.52020 19 101 19.02800 17.30747 9.04% 11.6 4361s 6862 2544 17.93162 14 100 19.02800 17.30747 9.04% 11.6 4416s 6863 2544 19.00679 18 100 19.02800 17.31057 9.03% 11.6 4600s 6864 2548 17.31057 14 87 19.02800 17.31057 9.03% 11.8 4701s 6866 2551 17.31057 15 89 19.02800 17.31057 9.03% 11.8 4765s 6870 2557 17.31057 16 92 19.02800 17.31057 9.03% 11.9 4823s 6878 2568 17.31057 17 94 19.02800 17.31057 9.03% 11.9 4889s 6893 2580 17.31057 18 83 19.02800 17.31057 9.03% 12.0 4965s 6922 2583 17.31057 19 86 19.02800 17.31057 9.03% 12.2 5032s 6954 2589 17.31057 20 88 19.02800 17.31057 9.03% 12.3 6305s 6986 2590 17.50787 20 51 19.02800 17.31057 9.03% 12.4 6341s 7018 2592 17.53896 21 54 19.02800 17.31057 9.03% 12.4 6537s 7050 2611 17.89280 21 59 19.02800 17.31057 9.03% 12.5 6564s 7112 2613 17.83990 23 49 19.02800 17.31057 9.03% 12.5 6593s 7172 2618 18.21932 24 47 19.02800 17.31057 9.03% 12.5 6631s 7232 2633 18.26972 25 54 19.02800 17.31057 9.03% 12.6 6649s 7314 2626 cutoff 26 19.02800 17.31057 9.03% 12.6 6692s 7392 2618 18.32379 28 47 19.02800 17.31057 9.03% 12.6 6720s 7477 2620 18.39289 29 43 19.02800 17.31057 9.03% 12.7 6758s 7578 2635 infeasible 31 19.02800 17.31057 9.03% 12.7 6807s 7687 2633 18.95446 30 43 19.02800 17.31057 9.03% 12.8 6837s 7795 2621 18.46969 32 41 19.02800 17.31057 9.03% 12.8 6870s 7919 2594 18.68957 34 36 19.02800 17.31057 9.03% 12.8 6922s 8037 2600 cutoff 36 19.02800 17.31057 9.03% 12.8 6973s 8152 2597 17.36211 20 51 19.02800 17.31057 9.03% 12.9 7003s 8262 2605 17.55447 22 53 19.02800 17.31057 9.03% 12.9 7047s 8393 2613 17.96711 27 48 19.02800 17.31057 9.03% 12.9 7074s 8538 2600 18.30654 32 48 19.02800 17.31057 9.03% 13.0 7125s 8698 2589 18.48297 34 13 19.02800 17.31057 9.03% 13.0 7167s 8855 2554 cutoff 40 19.02800 17.31057 9.03% 13.0 7474s 8933 2566 17.64436 22 52 19.02800 17.31057 9.03% 13.0 7525s 9142 2527 17.31057 22 51 19.02800 17.31057 9.03% 13.1 7582s 9318 2529 17.40023 24 43 19.02800 17.31057 9.03% 13.1 7628s 9523 2512 17.88729 24 36 19.02800 17.31057 9.03% 13.2 7666s 9741 2474 17.88729 25 37 19.02800 17.31057 9.03% 13.2 7713s 9953 2439 17.55819 28 54 19.02800 17.31057 9.03% 13.2 7760s 10174 2449 18.28484 31 43 19.02800 17.31057 9.03% 13.3 7802s 10403 2407 cutoff 38 19.02800 17.37807 8.67% 13.4 7849s 10652 2406 17.65322 23 76 19.02800 17.42002 8.45% 13.4 7892s 10908 2405 17.88414 30 61 19.02800 17.42002 8.45% 13.4 7933s 11180 2365 cutoff 40 19.02800 17.42173 8.44% 13.5 7980s 11461 2257 17.64701 26 48 19.02800 17.42173 8.44% 13.5 8027s 11561 2309 18.07776 27 50 19.02800 17.42173 8.44% 13.5 8078s 11837 2316 18.25284 32 27 19.02800 17.42173 8.44% 13.6 8133s 12137 2273 18.59749 34 27 19.02800 17.48304 8.12% 13.7 8187s 12485 2285 17.50350 22 54 19.02800 17.49049 8.08% 13.7 8241s 12895 2176 18.41154 30 42 19.02800 17.49049 8.08% 13.7 8294s 13067 2146 19.00535 35 26 19.02800 17.53091 7.87% 13.7 8349s 13503 2048 18.21816 23 33 19.02800 17.87613 6.05% 13.7 8405s 13912 1945 18.50346 31 35 19.02800 17.87887 6.04% 13.8 8468s 14369 1881 18.64694 33 39 19.02800 17.90581 5.90% 13.8 8526s 14828 1925 18.89525 40 15 19.02800 17.94218 5.71% 13.8 8594s 15376 1974 18.34879 34 52 19.02800 17.97810 5.52% 13.7 8658s 15939 1999 cutoff 33 19.02800 18.01312 5.33% 13.7 8734s 16465 2042 18.69770 33 28 19.02800 18.04090 5.19% 13.7 8812s Cutting planes: Gomory: 21 Cover: 14 MIR: 15 StrongCG: 2 Flow cover: 28 Inf proof: 2 Zero half: 123 Mod-K: 8 RLT: 54 Explored 17061 nodes (234416 simplex iterations) in 8812.81 seconds (8483.03 work units) Thread count was 32 (of 112 available processors) Solution count 10: 19.028 20.7987 20.9939 ... 39.84280 -
Hi Assia,
Even if the optimal value is 19.0279979 and Gurobi finds it at 692s, it doesn't stop there because it has to prove that this is indeed the optimal value. Quoting What is the MIP Gap?
Sometimes, Gurobi finds the global optimal solution early on while the current MIP gap is bigger than the allowed tolerance (e.g. current MIP gap of 40% vs an ε of 0.01%), so the rest of the optimization time is spent trying to get the certificate of optimality by pushing the dual bound towards the objective value of the incumbent solution.
At the point where the optimal value is found, the dual bound is 16.62000 and the MIPGap has a value of 12.7%, which is why Gurobi continues. Afterward, the dual bound takes a long time to reach 19.0279979.
Some parameters that might speed up the bound improvement are Cuts=2 or 3, or MIPFocus=3.
If this is not sufficient, you might want to consider strengthening the model formulation, for example by using User Cuts. You may also find the article General modeling tips to improve a formulation helpful.
Can you also share the model corresponding to the instance in the paper https://hrcak.srce.hr/file/285563? Maybe comparing both objective functions can give us some ideas on how to improve the formulation.
Thanks,
Elisabeth
0
Please sign in to leave a comment.
Comments
21 comments