About how to optimize the solver's speed for large optimization.
AnsweredI am running a large optimization problem for task scheduling. The ILP problem seems fine for 810 days of task scheduling. But when I run it for 31 days. It has taken so long, and still cannot reach any solution. Since I set a termination time, it just stops and reports no solution found yet. I used parameters
schedule_model.setParam('MIPGap', 0.1)
schedule_model.setParam('Timelimit', 100000)
I copy and pasted the solver's outcome below. Please let me know if there is any parameter we can set to expedite this process. Or should I simply wait for longer days for solutions? Many thanks!
Optimize a model with 4443771 rows, 17335093 columns and 151138704 nonzeros
Model fingerprint: 0xa20a9992
Variable types: 0 continuous, 17335093 integer (17335093 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+04]
Objective range [6e01, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+04]
Presolve removed 0 rows and 0 columns (presolve time = 13s) ...
Presolve removed 0 rows and 0 columns (presolve time = 16s) ...
Presolve removed 0 rows and 10743920 columns (presolve time = 23s) ...
Presolve removed 71629 rows and 10743920 columns (presolve time = 28s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 40s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 48s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 50s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 56s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 68s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 76s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 97s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 131s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 139s) ...
Presolve removed 71755 rows and 10744046 columns (presolve time = 158s) ...
Presolve removed 156759 rows and 10744046 columns (presolve time = 164s) ...
Presolve removed 156759 rows and 10744046 columns (presolve time = 176s) ...
Presolve removed 156759 rows and 10744046 columns (presolve time = 188s) ...
Presolve removed 156759 rows and 10744046 columns (presolve time = 190s) ...
Presolve removed 156759 rows and 10744046 columns (presolve time = 206s) ...
Presolve removed 162713 rows and 10750000 columns (presolve time = 217s) ...
Presolve removed 239270 rows and 10826557 columns (presolve time = 230s) ...
Presolve removed 239270 rows and 11042785 columns (presolve time = 246s) ...
Presolve removed 239270 rows and 11042785 columns (presolve time = 250s) ...
Presolve removed 240870 rows and 11042849 columns (presolve time = 259s) ...
Presolve removed 241671 rows and 11042849 columns (presolve time = 260s) ...
Presolve removed 294835 rows and 11042849 columns (presolve time = 265s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 270s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 283s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 285s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 290s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 295s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 300s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 305s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 310s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 315s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 320s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 325s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 330s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 335s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 340s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 345s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 350s) ...
Presolve removed 298732 rows and 11042849 columns (presolve time = 355s) ...
Presolve removed 298732 rows and 11042912 columns (presolve time = 365s) ...
Presolve removed 298858 rows and 11042912 columns (presolve time = 367s) ...
Presolve removed 298858 rows and 11042912 columns (presolve time = 371s) ...
Presolve removed 298858 rows and 11042912 columns (presolve time = 375s) ...
Presolve removed 299424 rows and 11260704 columns (presolve time = 384s) ...
Presolve removed 300862 rows and 11260704 columns (presolve time = 386s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 395s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 425s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 425s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 434s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 451s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 465s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 477s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 480s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 494s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 500s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 510s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 522s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 525s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 531s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 538s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 540s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 545s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 556s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 563s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 567s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 571s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 576s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 581s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 585s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 590s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 595s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 600s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 605s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 620s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 659s) ...
Presolve removed 308906 rows and 11267370 columns (presolve time = 666s) ...
Presolve removed 308906 rows and 11269757 columns (presolve time = 670s) ...
Presolve removed 308906 rows and 11274198 columns (presolve time = 675s) ...
Presolve removed 308906 rows and 11280491 columns (presolve time = 680s) ...
Presolve removed 308906 rows and 11282618 columns (presolve time = 685s) ...
Presolve removed 308906 rows and 11284896 columns (presolve time = 690s) ...
Presolve removed 308906 rows and 11286388 columns (presolve time = 695s) ...
Presolve removed 308906 rows and 11289469 columns (presolve time = 700s) ...
Presolve removed 308906 rows and 11292380 columns (presolve time = 705s) ...
Presolve removed 308906 rows and 11296347 columns (presolve time = 710s) ...
Presolve removed 308906 rows and 11300913 columns (presolve time = 715s) ...
Presolve removed 308906 rows and 11305535 columns (presolve time = 720s) ...
Presolve removed 308906 rows and 11310789 columns (presolve time = 725s) ...
Presolve removed 308906 rows and 11316419 columns (presolve time = 730s) ...
Presolve removed 308906 rows and 11322708 columns (presolve time = 735s) ...
Presolve removed 308906 rows and 11326801 columns (presolve time = 740s) ...
Presolve removed 308906 rows and 11331862 columns (presolve time = 745s) ...
Presolve removed 308906 rows and 11334974 columns (presolve time = 750s) ...
Presolve removed 308906 rows and 11334974 columns (presolve time = 755s) ...
Presolve removed 308906 rows and 11334974 columns (presolve time = 760s) ...
Presolve removed 308906 rows and 11334974 columns (presolve time = 765s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 770s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 776s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 788s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 790s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 795s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 800s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 805s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 810s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 815s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 820s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 825s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 830s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 835s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 840s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 845s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 850s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 855s) ...
Presolve removed 311260 rows and 11334974 columns (presolve time = 1421s) ...
Presolve removed 311260 rows and 11512791 columns (presolve time = 1425s) ...
Presolve removed 506680 rows and 11514519 columns (presolve time = 1431s) ...
Presolve removed 506680 rows and 11514519 columns (presolve time = 1435s) ...
Presolve removed 506680 rows and 11514519 columns (presolve time = 1441s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1447s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1451s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1457s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1470s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1485s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1499s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1505s) ...
Presolve removed 506684 rows and 11514521 columns (presolve time = 1521s) ...
Presolve removed 531785 rows and 11514521 columns (presolve time = 1536s) ...
Presolve removed 531785 rows and 11514521 columns (presolve time = 1545s) ...
Presolve removed 531785 rows and 11514521 columns (presolve time = 1545s) ...
Presolve removed 531785 rows and 11514521 columns (presolve time = 1560s) ...
Presolve removed 531817 rows and 11514553 columns (presolve time = 1566s) ...
Presolve removed 531817 rows and 11514553 columns (presolve time = 1573s) ...
Presolve removed 531817 rows and 11514553 columns (presolve time = 1580s) ...
Presolve removed 531817 rows and 11514553 columns (presolve time = 1589s) ...
Presolve removed 531817 rows and 11514553 columns (presolve time = 1590s) ...
Presolve removed 533141 rows and 11514745 columns (presolve time = 1596s) ...
Presolve removed 533479 rows and 11514745 columns (presolve time = 1600s) ...
Presolve removed 534970 rows and 11514745 columns (presolve time = 1605s) ...
Presolve removed 535098 rows and 11514745 columns (presolve time = 1610s) ...
Presolve removed 535354 rows and 11514745 columns (presolve time = 1616s) ...
Presolve removed 535610 rows and 11514905 columns (presolve time = 1621s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1627s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1632s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1635s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1641s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1654s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1667s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1677s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1682s) ...
Presolve removed 574472 rows and 11540664 columns (presolve time = 1695s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1709s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1718s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1720s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1729s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1734s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1742s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1747s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1756s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1760s) ...
Presolve removed 574500 rows and 11540664 columns (presolve time = 1768s) ...
Presolve removed 574550 rows and 11540664 columns (presolve time = 1770s) ...
Presolve removed 574666 rows and 11540664 columns (presolve time = 1775s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1780s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1786s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1791s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1798s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1805s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1805s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1810s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1815s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1820s) ...
Presolve removed 574699 rows and 11540664 columns (presolve time = 1825s) ...
Presolve removed 574699 rows and 11541294 columns (presolve time = 1830s) ...
Presolve removed 574699 rows and 11541294 columns (presolve time = 1835s) ...
Presolve removed 574699 rows and 11541294 columns (presolve time = 1840s) ...
Presolve removed 574909 rows and 11541294 columns (presolve time = 1846s) ...
Presolve removed 575539 rows and 11541294 columns (presolve time = 1853s) ...
Presolve removed 575539 rows and 11541294 columns (presolve time = 1855s) ...
Presolve removed 575539 rows and 11541294 columns (presolve time = 1872s) ...
Presolve removed 575539 rows and 11541294 columns (presolve time = 1888s) ...
Presolve removed 572531 rows and 11538286 columns
Presolve time: 1888.52s
Presolved: 3871240 rows, 5796807 columns, 97758679 nonzeros
Variable types: 0 continuous, 5796807 integer (5795527 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 2.97s
Barrier statistics:
Dense cols : 5652
AA' NZ : 3.619e+07
Factor NZ : 1.059e+08 (roughly 2.3 GB of memory)
Factor Ops : 3.683e+11 (roughly 7 seconds per iteration)
Threads : 17
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 3.88467558e+03 6.75909235e+04 6.10e+04 2.19e01 1.07e+02 2220s
1 2.46095013e+03 2.20866878e+06 3.35e+04 5.88e01 5.76e+01 2224s
2 1.53019190e+03 3.08473758e+06 1.67e+04 2.65e01 2.86e+01 2227s
3 1.16580986e+03 3.09383474e+06 1.02e+04 1.13e01 1.75e+01 2230s
4 6.61563010e+02 2.43557956e+06 1.44e+03 1.03e01 2.70e+00 2235s
5 4.82038853e+02 1.44432898e+06 7.05e+02 4.51e02 1.26e+00 2238s
6 3.57552891e+02 1.02838037e+06 2.60e+02 2.87e02 5.38e01 2242s
7 3.26000950e+02 3.41486603e+05 1.01e+02 1.41e02 1.86e01 2245s
8 3.19061986e+02 1.15607495e+05 3.72e+01 3.73e03 6.43e02 2248s
9 3.34097824e+02 9.30188749e+04 1.67e+01 2.89e03 3.62e02 2252s
10 3.46336249e+02 4.58373903e+04 1.03e+01 1.27e03 1.97e02 2255s
11 3.47558388e+02 2.48572482e+04 5.68e+00 6.04e04 1.06e02 2259s
12 3.26685305e+02 9.76206900e+03 1.14e+00 2.07e04 2.95e03 2262s
13 2.97099999e+02 7.72477620e+03 5.85e01 1.69e04 2.03e03 2265s
14 2.86528601e+02 5.67219772e+03 4.74e01 1.28e04 1.55e03 2269s
15 2.65563962e+02 5.20397088e+03 3.43e01 1.18e04 1.33e03 2273s
Barrier performed 15 iterations in 2273.13 seconds (1359.74 work units)
Barrier solve interrupted  model solved by another algorithm
Concurrent spin time: 96.89s (can be avoided by choosing Method=3)
Solved with dual simplex
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
106708 1.7308972e+02 0.000000e+00 0.000000e+00 2277s
Use crossover to convert LP symmetric solution to basic solution...
Root crossover log...
20770 DPushes remaining with DInf 1.6431239e04 2289s
2035 DPushes remaining with DInf 1.3947156e04 2291s
0 DPushes remaining with DInf 1.3947156e04 2292s
33190 PPushes remaining with PInf 0.0000000e+00 2293s
14421 PPushes remaining with PInf 6.1546377e05 2295s
0 PPushes remaining with PInf 5.0968885e05 2299s
Push phase complete: Pinf 5.0968885e05, Dinf 1.2611250e+02 2300s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
159549 1.7308972e+02 0.000000e+00 1.261125e+02 2305s
159982 1.7308972e+02 5.096889e05 0.000000e+00 2310s
159996 1.7308972e+02 0.000000e+00 0.000000e+00 2317s
159996 1.7308972e+02 0.000000e+00 0.000000e+00 2328s
Root relaxation: objective 1.730897e+02, 159996 iterations, 361.60 seconds (165.25 work units)
Total elapsed time = 2336.71s
Total elapsed time = 2423.60s
Total elapsed time = 2482.18s
Total elapsed time = 2522.27s
Total elapsed time = 2566.19s
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 173.08972 0 8385  173.08972   3112s
0 0 325.50076 0 21525  325.50076   29949s
0 0 325.50076 0 21039  325.50076   30025s
0 0 325.50076 0 20915  325.50076   30066s
Cutting planes:
Learned: 1149
Gomory: 61
Cover: 936
Clique: 3182
MIR: 8
Flow cover: 357
GUB cover: 478
Zero half: 211
RLT: 10
Relaxandlift: 11
BQP: 74
Explored 1 nodes (702894 simplex iterations) in 100004.53 seconds (78595.89 work units)
Thread count was 20 (of 40 available processors)
Solution count 0
Time limit reached
Best objective , best bound 3.255250000000e+02, gap 
CPU times: total: 1d 11h 13min 4s
Wall time: 1d 3h 46min 44s

Which version of Gurobi did you use? Please always use the latest version (currently 10.0.1).
You could try telling Gurobi to focus more on feasible points via the parameters MIPFocus=1 and by using the No Relaxation heuristic controlled by the NoRelHeurTime parameter. From the log, I would try setting NoRelHeurTime=3600 as a first experiment. You could also have a look at the list of Most important parameters for MIPs.
Please note that your model is really huge with over 17 million binary variables. Thus, it is somewhat expected that solution will take more that usual. Anyway, there is one thing which is suspicious. The big gap without any log output
0 0 173.08972 0 8385  173.08972   3112s
27k seconds without log output
0 0 325.50076 0 21525  325.50076   29949s
[...]
0 0 325.50076 0 20915  325.50076   30066s
> jump to time limit of 100k seconds, i.e., 70k seconds no output.Could you please share this model such that I could have a closer look? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 
Thank you! Let me first make a saved model to . mps file as soon as I can and then figure out how to share it to community with your link.
0 
Do you expect to see the .mps model or the code to generate the model? The .mps model is 5.5GB. If it is too large, I have to schedule a shorter period so that you may just scan it for potential problems..
0 
If you can reproduce the behavior where there is no output for a very long period of time with a smaller model, then a smaller model would definitely suffice.
Otherwise, you could just compress the .mps file. Size of the model is not a problem on my side as long as I can reproduce the issue, so you don't have to share your code.
0 
Great. the zipped file is around 550MB. I hope I can upload from here.
0 
The mode is uploaded to this dropbox link:
https://www.dropbox.com/s/yujwy4h6oyu9xzd/workindv_model.zip?dl=0
Many thanks
0 
Unfortunately, I am not able to expand the file. I get the error
Unable to expand "workindv_model.zip" into "Downloads"
(Error 79  inappropriate file type or format.)Also automatic extracting in dropbox results in an error
1 file couldn't be automatically unzipped.
Could you please try again?
0 
I apologize for the inconvenience. I put an unzip version and please see if it works. I also set the Dropbox access permission for anyone beyond our university scope.
https://www.dropbox.com/s/a1c8khi9nw5c6rz/workindv_model.mps?dl=0
Thank you so much for the great patience with me!
0 
I was able to reproduce the issue on my side and am investigating. Unfortunately, at this point I cannot tell whether it is an actual bug or just expected behavior due to the model size. I will let you know here, when I find something.
It definitely looks like finding a first feasible point is a big issue for this model. You could try running NoRelHeurTime=20000 which will run a special heuristic before solving the root node relaxation for 20k seconds (1/5th of your overall time). Maybe the heuristic is able to find a first feasible solution and the overall optimization run is then better.
0 
Reading this topic, it came to my mind that lazy constraints or the partition heuristic might help address the problem?
0 
Thank you, Jaromil, I will try the heuristics.
Thoms, do you have any guidance tuning the lazy constraints and partition heuristic?
0 
Hi whwhwh55,
besides the official gurobi articels I don't have additional guidance:Lazy constraints:
https://support.gurobi.com/hc/enus/articles/360013197972
https://www.gurobi.com/documentation/10.0/refman/lazy.html#attr:Lazy
Since your problem has a lot of (linear) constraints, some of them might be inactive and may remain in the lazy constraint pool, for example constraints for rare special cases of your task scheduling. But this is just a guess  I don't know your problem.Partition Heuristic:
https://www.gurobi.com/documentation/10.0/refman/partition.html
I don't know your problem, so I don't know if your vars can be splitted into different groups.Maybe spending more time for presolve could also help:
https://www.gurobi.com/documentation/10.0/refman/presolve.html#parameter:Presolve0 
Thank you!
0
Please sign in to leave a comment.
Comments
13 comments