Unable to find optimal solution for some instances
Answered
Hi,
I am dealing with a scheduling problem and I use pulp and gurobi to solve it. While the solver works very well for some instances, for others it can't find the optimal solution even when running for 2 days. I don't think it's a size problem since the solver has already solved much larger problems successfully (Please see attached image - Note: For instances 11 & 12 I use Lagrangian relaxation).
My whole formulation has only binary variables. Please see the gurobi log below;
---Instance 10---
Set parameter Threads to value 7
Set parameter TimeLimit to value 600
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 7 threads
Optimize a model with 9005 rows, 101210 columns and 569260 nonzeros
Model fingerprint: 0xc6d777c5
Variable types: 0 continuous, 101210 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 8e+01]
Objective range [1e+00, 6e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 1781738.0000
Presolve removed 1872 rows and 0 columns
Presolve time: 0.45s
Presolved: 7133 rows, 101210 columns, 437788 nonzeros
Variable types: 0 continuous, 101210 integer (101210 binary)
Found heuristic solution: objective 1051274.0000
Root relaxation: objective 2.262222e+02, 4723 iterations, 0.64 seconds (1.15 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 226.22222 0 24 1051274.00 226.22222 100% - 2s
H 0 0 40619.000000 226.22222 99.4% - 3s
H 0 0 11083.000000 226.22222 98.0% - 3s
0 0 226.22222 0 350 11083.0000 226.22222 98.0% - 6s
H 0 0 10659.000000 226.22222 97.9% - 10s
0 0 417.00000 0 248 10659.0000 417.00000 96.1% - 15s
H 0 0 1275.0000000 417.00000 67.3% - 16s
0 0 417.00000 0 230 1275.00000 417.00000 67.3% - 16s
0 0 417.00000 0 166 1275.00000 417.00000 67.3% - 19s
0 0 417.00000 0 92 1275.00000 417.00000 67.3% - 28s
H 0 0 871.0000000 417.00000 52.1% - 28s
0 0 417.00000 0 390 871.00000 417.00000 52.1% - 30s
0 0 619.00000 0 479 871.00000 619.00000 28.9% - 40s
0 0 619.00000 0 510 871.00000 619.00000 28.9% - 40s
H 0 0 851.0000000 619.00000 27.3% - 41s
0 0 619.00000 0 120 851.00000 619.00000 27.3% - 45s
0 0 619.00000 0 354 851.00000 619.00000 27.3% - 46s
0 0 619.00000 0 659 851.00000 619.00000 27.3% - 49s
0 0 619.00000 0 76 851.00000 619.00000 27.3% - 54s
0 2 619.00000 0 74 851.00000 619.00000 27.3% - 58s
1 4 619.00000 1 310 851.00000 619.00000 27.3% 8750 62s
3 7 619.00000 2 423 851.00000 619.00000 27.3% 3820 65s
7 14 821.00000 3 448 851.00000 619.00000 27.3% 2205 75s
14 21 821.00000 4 522 851.00000 619.00000 27.3% 2184 87s
21 28 821.00000 4 555 851.00000 619.00000 27.3% 2815 94s
28 35 821.00000 5 570 851.00000 619.00000 27.3% 2561 143s
35 43 821.00000 6 539 851.00000 619.00000 27.3% 2182 149s
43 51 821.00000 6 505 851.00000 619.00000 27.3% 1941 155s
51 61 821.00000 7 453 851.00000 619.00000 27.3% 1731 160s
61 69 821.00000 9 426 851.00000 619.00000 27.3% 1596 165s
69 98 821.00000 10 452 851.00000 619.00000 27.3% 1479 175s
98 187 821.00000 13 391 851.00000 619.00000 27.3% 1209 205s
187 306 821.00000 20 273 851.00000 619.00000 27.3% 898 285s
306 697 831.00000 33 287 851.00000 619.00000 27.3% 753 397s
705 1164 831.00000 76 193 851.00000 619.00000 27.3% 585 533s
1235 1360 831.00000 133 142 851.00000 619.00000 27.3% 461 600s
Cutting planes:
Cover: 397
Clique: 238
MIR: 31
StrongCG: 2
GUB cover: 217
Zero half: 55
RLT: 9
Explored 1482 nodes (774113 simplex iterations) in 600.10 seconds (1010.03 work units)
Thread count was 7 (of 8 available processors)
Solution count 9: 851 871 1275 ... 1.78174e+06
Time limit reached
Best objective 8.510000000000e+02, best bound 6.190000000000e+02, gap 27.2620%
Gurobi status= 9
Instances 11 & 12 have similar log outputs. Is there anything I could do to improve the performance? I would be very grateful if anyone could help.
Thank you in advance.
Kind regards,
Yaroslav Pylyavskyy
-
Hi Yaroslav,
You could try experimenting with most important parameters for MIPs.
Did you try to not use the Lagrangian relaxation? Moving constraints to the objective function with penalty terms often leads to numerical problems and a weak relaxation.
Maybe our recent Tech Talk on weak & strong MIP formulations might be of interest.
Best regards,
Jaromił1 -
Hi Jaromil,
Thank you for your reply and the resources provided.
Yes, I tried without Lagrangian relaxation but it gives an infeasible solution. That is why I use it actually, to relax some hard constraints and get a feasible solution.
Best regards,
Yaroslav
0 -
Hi Yaroslav,
When you noticed that your model is infeasible, did you try determining why? The Knowledge Base article How do I determine why my model is infeasible? is helpful here.
I think that it is best to try to find out why your model is infeasible instead of using Lagrangian relaxation which is often numerically unstable.
Best regards,
Jaromił0 -
Hi Jaromil,
Yes, I found which constraints were responsible for infeasibility.
By the way, for instance 10 I am not using Lagrangian relaxation as the model is feasible. However, the solver gets stuck at 0.15% gap and could run for 2 days without finding optimal solution.
Which alternative method would you recommend to Lagrangian relaxation?
Best regards,
Yaroslav
0 -
Hi Yaroslav,
I am not aware of any other general method which would fit here. You could try to strengthen your formulation, see our Tech Talk on Weak & Strong Formulations.
You could also try finding parameters to improve convergence, see Most important parameters for MIP.
The most important question would be: How accurate is your model? Do you really need a MIPGap that is better than 0.15% or would already a 0.5% or even a 1% gap be enough for your application? For MIPs, closing the last few percent is often the hardest part and takes the longest time.
Best regards,
Jaromił1 -
Hi Jaromil,
I just wanted to report to you something odd that I noticed regarding gurobi's performance between pulp and gurobipy. It seems that gurobi's performance is better when using pulp, instead of gurobipy. Please see below logs.
Pulp
Set parameter Threads to value 7
Set parameter TimeLimit to value 65
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 7 threads
Optimize a model with 9005 rows, 100810 columns and 565110 nonzeros
Model fingerprint: 0xc55f00a6
Variable types: 0 continuous, 100810 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+01]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve removed 1901 rows and 29 columns
Presolve time: 0.47s
Presolved: 7104 rows, 100781 columns, 435452 nonzeros
Variable types: 0 continuous, 100781 integer (100781 binary)Root relaxation: objective 2.021500e+04, 4702 iterations, 0.59 seconds (0.89 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 20215.0000 0 36 - 20215.0000 - - 2s
H 0 0 270215.00000 20215.0000 92.5% - 3s
0 0 20215.0000 0 452 270215.000 20215.0000 92.5% - 5s
H 0 0 50215.000000 20215.0000 59.7% - 9s
0 0 20215.0000 0 452 50215.0000 20215.0000 59.7% - 9s
0 0 20215.0000 0 665 50215.0000 20215.0000 59.7% - 17s
H 0 0 20245.000000 20215.0000 0.15% - 18s
0 0 20215.0000 0 671 20245.0000 20215.0000 0.15% - 20s
0 0 20215.0000 0 332 20245.0000 20215.0000 0.15% - 24s
0 0 20215.0000 0 47 20245.0000 20215.0000 0.15% - 34s
0 0 20215.0000 0 207 20245.0000 20215.0000 0.15% - 37s
0 0 20215.0000 0 173 20245.0000 20215.0000 0.15% - 44s
0 0 20215.0000 0 44 20245.0000 20215.0000 0.15% - 48s
0 0 20215.0000 0 88 20245.0000 20215.0000 0.15% - 49s
0 0 20215.0000 0 45 20245.0000 20215.0000 0.15% - 54s
0 0 20215.0000 0 22 20245.0000 20215.0000 0.15% - 55s
0 2 20215.0000 0 20 20245.0000 20215.0000 0.15% - 59s
1 5 20215.0000 1 251 20245.0000 20215.0000 0.15% 10552 65sCutting planes:
Cover: 85
Clique: 319
MIR: 22
StrongCG: 1
GUB cover: 58
Zero half: 39
RLT: 3Explored 3 nodes (180712 simplex iterations) in 65.14 seconds (89.12 work units)
Thread count was 7 (of 8 available processors)Solution count 4: 20245 20245 50215 270215
Time limit reached
Best objective 2.024500000000e+04, best bound 2.021500000000e+04, gap 0.1482%
Gurobi status= 9Gurobipy
Set parameter Threads to value 7
Set parameter TimeLimit to value 65
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 7 threads
Optimize a model with 9005 rows, 100810 columns and 565110 nonzeros
Model fingerprint: 0xb2ddc278
Variable types: 0 continuous, 100810 integer (100810 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+01]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve removed 1901 rows and 29 columns
Presolve time: 0.49s
Presolved: 7104 rows, 100781 columns, 435452 nonzeros
Variable types: 0 continuous, 100781 integer (100781 binary)Root relaxation: objective 2.021500e+04, 4828 iterations, 0.72 seconds (1.08 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 20215.0000 0 12 - 20215.0000 - - 2s
H 0 0 140215.00000 20215.0000 85.6% - 3s
H 0 0 60215.000000 20215.0000 66.4% - 3s
0 0 20215.0000 0 213 60215.0000 20215.0000 66.4% - 4s
H 0 0 50215.000000 20215.0000 59.7% - 8s
0 0 20215.0000 0 41 50215.0000 20215.0000 59.7% - 13s
0 0 20215.0000 0 204 50215.0000 20215.0000 59.7% - 14s
0 0 20215.0000 0 53 50215.0000 20215.0000 59.7% - 18s
0 0 20215.0000 0 146 50215.0000 20215.0000 59.7% - 21s
0 0 20215.0000 0 34 50215.0000 20215.0000 59.7% - 25s
0 0 20215.0000 0 9 50215.0000 20215.0000 59.7% - 27s
H 0 0 30215.000000 20215.0000 33.1% - 27s
0 0 20215.0000 0 28 30215.0000 20215.0000 33.1% - 41s
0 0 20215.0000 0 266 30215.0000 20215.0000 33.1% - 42s
0 0 20215.0000 0 323 30215.0000 20215.0000 33.1% - 48s
0 0 20215.0000 0 142 30215.0000 20215.0000 33.1% - 54s
0 0 20215.0000 0 419 30215.0000 20215.0000 33.1% - 55s
H 0 0 20345.000000 20215.0000 0.64% - 62s
H 0 0 20285.000000 20215.0000 0.35% - 62s
H 0 0 20255.000000 20215.0000 0.20% - 62s
0 0 20215.0000 0 69 20255.0000 20215.0000 0.20% - 62s
0 0 20215.0000 0 18 20255.0000 20215.0000 0.20% - 64sCutting planes:
Cover: 126
Clique: 388
MIR: 24
StrongCG: 2
GUB cover: 111
Zero half: 67
Mod-K: 8
RLT: 4Explored 1 nodes (229029 simplex iterations) in 65.02 seconds (77.46 work units)
Thread count was 7 (of 8 available processors)Solution count 7: 20255 20285 20345 ... 140215
Time limit reached
Best objective 2.025500000000e+04, best bound 2.021500000000e+04, gap 0.1975%Any thoughts on why this happens?
Best regards,
Yaroslav
0 -
Hi Yaroslav,
The exact same optimization path is only reproducible for the exact same model and parameters on the same machine, see Is Gurobi Optimizer deterministic? I don't know Pulp well, but it may be possible that the ordering of variables and/or constraints is changed during model building in pulp compared to gurobipy which would already explain the different solution path.
You can see that the two models you solve are not exactly the same by comparing the fingerprint.
Best regards,
Jaromił1 -
Thanks Jaromil! Indeed, that makes sense.
Best regards,
Yaroslav
0
Please sign in to leave a comment.
Comments
8 comments