How to speed up MILP model to find the solution?
Answered
Hi everyone
I'm solving a MILP model but I found it's hard for gurobi to find a solution despite the parameter MIPFocus set to 3.Here is the log:
Removed 217 duplicated or redundant inequalities
Transfered 2354 inequalities to equalities
Set parameter Username
Set parameter MIPGap to value 0.03
Set parameter CrossoverBasis to value 0
Set parameter MIPFocus to value 3
Set parameter NodefileDir to value ""
Set parameter PreSOS2BigM to value 0
Set parameter TuneTrials to value 3
Academic license - for non-commercial use only - expires 2023-12-04
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 28835 rows, 14683 columns and 440274 nonzeros
Model fingerprint: 0x79738ad3
Variable types: 8590 continuous, 6093 integer (6093 binary)
Coefficient statistics:
Matrix range [1e-03, 1e+04]
Objective range [1e+01, 1e+03]
Bounds range [1e+00, 1e+00]
RHS range [3e-01, 1e+04]
Presolve removed 25014 rows and 10950 columns
Presolve time: 0.15s
Presolved: 3821 rows, 3733 columns, 14172 nonzeros
Variable types: 1751 continuous, 1982 integer (1982 binary)
Found heuristic solution: objective -213869.9891
Root relaxation presolve removed 1090 rows and 1088 columns
Root relaxation presolved: 2731 rows, 2645 columns, 11978 nonzeros
Extra simplex iterations after uncrush: 5
Root relaxation: objective -1.613927e+07, 1668 iterations, 0.03 seconds (0.04 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -1.614e+07 0 674 -213869.99 -1.614e+07 7446% - 1s
0 0 -1.273e+07 0 755 -213869.99 -1.273e+07 5853% - 1s
0 0 -1.009e+07 0 794 -213869.99 -1.009e+07 4619% - 2s
0 0 -9507459.3 0 802 -213869.99 -9507459.3 4345% - 2s
0 0 -9471290.2 0 820 -213869.99 -9471290.2 4329% - 2s
0 0 -9453711.1 0 818 -213869.99 -9453711.1 4320% - 2s
0 0 -9448172.2 0 820 -213869.99 -9448172.2 4318% - 2s
0 0 -9447782.1 0 821 -213869.99 -9447782.1 4318% - 2s
H 0 0 -284212.3740 -9447782.1 3224% - 2s
H 0 0 -392771.9962 -8792865.7 2139% - 3s
H 0 0 -592230.5845 -8792865.7 1385% - 3s
0 0 -8792865.7 0 820 -592230.58 -8792865.7 1385% - 4s
H 0 0 -628695.2468 -8733168.6 1289% - 4s
H 0 0 -672250.2602 -8733168.6 1199% - 4s
H 0 0 -702131.0252 -8733168.6 1144% - 4s
0 0 -8733168.6 0 843 -702131.03 -8733168.6 1144% - 4s
0 0 -8720433.0 0 853 -702131.03 -8720433.0 1142% - 4s
0 0 -8719772.4 0 858 -702131.03 -8719772.4 1142% - 4s
H 0 0 -997212.8047 -8719772.4 774% - 4s
H 0 0 -997719.2583 -8333031.5 735% - 5s
0 0 -8331009.4 0 785 -997719.26 -8331009.4 735% - 6s
0 0 -8306057.6 0 828 -997719.26 -8306057.6 733% - 6s
0 0 -8303423.8 0 845 -997719.26 -8303423.8 732% - 6s
0 0 -8040813.5 0 777 -997719.26 -8040813.5 706% - 10s
0 0 -8020862.5 0 769 -997719.26 -8020862.5 704% - 10s
0 0 -8018503.2 0 772 -997719.26 -8018503.2 704% - 10s
0 0 -7879548.5 0 731 -997719.26 -7879548.5 690% - 12s
0 0 -7872291.5 0 750 -997719.26 -7872291.5 689% - 12s
0 0 -7753751.8 0 739 -997719.26 -7753751.8 677% - 15s
0 0 -7748340.1 0 728 -997719.26 -7748340.1 677% - 16s
0 2 -7748340.1 0 728 -997719.26 -7748340.1 677% - 17s
31 40 -7221944.0 6 716 -997719.26 -7373210.8 639% 467 21s
63 72 -7229358.6 6 717 -997719.26 -7231921.9 625% 425 25s
H 223 244 -1005532.598 -7123852.9 608% 270 28s
460 490 -6915279.8 9 665 -1005532.6 -7063644.9 602% 239 30s
H 581 602 -1005681.584 -7035889.9 600% 239 32s
H 585 602 -1008477.330 -7034141.3 598% 239 32s
H 592 602 -1013391.523 -7029042.2 594% 239 32s
H 595 602 -1017939.988 -7028853.4 590% 238 32s
923 942 -6827120.9 6 671 -1017940.0 -6954055.5 583% 238 35s
1337 1398 -6749427.4 10 697 -1017940.0 -6880769.1 576% 244 40s
H 1455 1456 -1044170.314 -6870048.2 558% 247 46s
1459 1459 -6757804.7 11 769 -1044170.3 -6870048.2 558% 246 51s
H 1466 1390 -1044803.503 -6870048.2 558% 245 57s
H 1466 1320 -1044915.242 -6870048.2 557% 245 57s
1468 1321 -6164800.2 13 816 -1044915.2 -6870048.2 557% 245 60s
1471 1323 -6739801.3 12 747 -1044915.2 -6870048.2 557% 244 66s
1473 1324 -5844022.7 15 785 -1044915.2 -6870048.2 557% 244 70s
1478 1328 -6388694.0 13 793 -1044915.2 -6781677.7 549% 243 76s
H 1478 1262 -1045130.769 -6781677.7 549% 243 78s
H 1478 1198 -1045242.508 -6781677.7 549% 243 78s
1480 1199 -6595057.9 12 794 -1045242.5 -6694451.4 540% 243 80s
H 1481 1140 -1045743.287 -6691589.5 540% 243 82s
H 1485 1084 -1045980.968 -6549131.8 526% 242 84s
H 1486 1030 -1047745.455 -6549131.8 525% 242 86s
H 1490 981 -1048214.148 -6478604.5 518% 241 90s
1494 983 -6144313.3 11 778 -1048214.1 -6319803.0 503% 241 96s
1497 985 -5681999.1 17 764 -1048214.1 -6242616.6 496% 240 101s
1501 988 -6235804.7 11 735 -1048214.1 -6235804.7 495% 239 105s
H 1502 939 -1048348.338 -6230541.8 494% 239 107s
1504 940 -6225221.0 10 774 -1048348.3 -6225221.0 494% 239 110s
1508 943 -5935802.5 9 768 -1048348.3 -6204980.1 492% 238 116s
1510 944 -5927548.3 15 768 -1048348.3 -6175246.5 489% 238 120s
1511 947 -5961553.2 14 734 -1048348.3 -6171435.2 489% 260 130s
1534 976 -5657681.2 18 781 -1048348.3 -5755310.5 449% 267 136s
1550 987 -5512390.6 19 791 -1048348.3 -5656936.4 440% 271 140s
1582 1008 -5358079.6 18 772 -1048348.3 -5505513.5 425% 289 145s
1598 1019 -5340259.5 20 731 -1048348.3 -5476240.9 422% 300 151s
H 1599 970 -1048858.385 -5476240.9 422% 300 151s
H 1600 924 -1049206.672 -5476056.4 422% 301 151s
H 1607 879 -1049850.910 -5466433.8 421% 306 151s
1630 903 -5285654.0 21 683 -1049850.9 -5412597.2 416% 320 156s
H 1646 872 -1049951.065 -5387714.0 413% 329 160s
H 1651 831 -1050051.221 -5378644.0 412% 331 160s
1694 865 -5208970.6 19 726 -1050051.2 -5346980.4 409% 358 166s
1731 896 -5312230.7 21 665 -1050051.2 -5329766.2 408% 374 171s
H 1780 885 -1051861.871 -5310531.9 405% 391 180s
H 1781 850 -1052835.774 -5310167.3 404% 391 180s
H 1791 812 -1054362.510 -5304583.7 403% 396 180s
1821 857 -5193963.2 21 717 -1054362.5 -5293091.7 402% 406 185s
1881 883 -5044227.9 21 684 -1054362.5 -5280757.2 401% 424 194s
1897 916 -5159223.8 22 713 -1054362.5 -5269686.6 400% 430 197s
1975 980 -5024648.3 20 672 -1054362.5 -5255414.8 398% 447 202s
2025 1016 -5136487.4 23 664 -1054362.5 -5248141.8 398% 454 205s
2121 1079 -5120778.5 23 673 -1054362.5 -5233888.6 396% 467 210s
2230 1151 -5105082.4 23 644 -1054362.5 -5222106.1 395% 480 216s
2332 1234 -5170571.1 22 619 -1054362.5 -5211044.2 394% 493 221s
2489 1349 -5084168.1 21 668 -1054362.5 -5198754.5 393% 500 226s
2605 1456 -5141042.7 21 628 -1054362.5 -5186365.2 392% 507 231s
2838 1602 -5107784.9 23 660 -1054362.5 -5175038.6 391% 505 236s
3050 1654 -5042421.3 23 654 -1054362.5 -5167868.3 390% 505 242s
3094 1750 -5101022.5 22 645 -1054362.5 -5162901.1 390% 508 245s
3343 1907 -4890220.4 22 693 -1054362.5 -5153673.4 389% 509 250s
3646 2227 -5006447.5 22 688 -1054362.5 -5146261.5 388% 504 255s
4033 2603 -4903004.1 23 606 -1054362.5 -5135704.3 387% 492 260s
4221 2676 -4797247.3 23 602 -1054362.5 -5129702.5 387% 489 265s
4492 2868 -4776251.9 22 600 -1054362.5 -5121737.6 386% 489 301s
4512 2958 -4753701.4 25 605 -1054362.5 -5115818.6 385% 492 307s
H 4528 2958 -1056828.385 -5115670.6 384% 492 307s
H 4535 2958 -1057216.402 -5114713.2 384% 492 307s
4606 3152 -4829804.9 23 650 -1057216.4 -5110131.4 383% 494 310s
4816 3194 -4784910.8 25 669 -1057216.4 -5107377.4 383% 494 316s
5073 3565 -4715136.8 21 607 -1057216.4 -5092670.4 382% 499 323s
5264 3761 infeasible 24 -1057216.4 -5086757.0 381% 503 326s
5468 4004 -4645599.7 24 572 -1057216.4 -5081520.8 381% 507 330s
5954 4438 infeasible 23 -1057216.4 -5063153.1 379% 510 339s
6195 4662 -4633331.2 24 583 -1057216.4 -5053416.2 378% 514 343s
6437 4907 -4700197.0 25 544 -1057216.4 -5045881.2 377% 517 347s
6694 5138 infeasible 25 -1057216.4 -5040524.8 377% 518 351s
H 6945 5172 -1057325.751 -5034810.6 376% 522 361s
H 6956 5172 -1057626.112 -5031304.5 376% 522 361s
H 6977 5172 -1057735.462 -5027995.4 375% 523 361s
6987 5437 infeasible 23 -1057735.5 -5027232.0 375% 524 365s
7266 5589 -4595610.6 26 567 -1057735.5 -5017662.6 374% 526 375s
7426 5954 -4543944.2 27 545 -1057735.5 -5010726.6 374% 526 380s
7797 6328 infeasible 24 -1057735.5 -5001183.3 373% 523 385s
8175 6702 -4655063.2 25 590 -1057735.5 -4991650.4 372% 521 390s
8559 7046 -4632512.0 25 596 -1057735.5 -4985002.9 371% 521 395s
8909 7411 -4529162.5 27 569 -1057735.5 -4978826.7 371% 522 401s
9288 7815 -4582906.8 25 593 -1057735.5 -4965003.2 369% 522 407s
9700 8210 -4638521.9 22 620 -1057735.5 -4953979.5 368% 522 413s
10105 8620 infeasible 23 -1057735.5 -4945622.3 368% 522 419s
10537 9098 -4593474.3 24 602 -1057735.5 -4935598.6 367% 522 425s
11029 9573 -4421246.3 26 642 -1057735.5 -4926137.1 366% 520 432s
11516 10087 -4690543.3 25 608 -1057735.5 -4918007.1 365% 521 439s
12050 10403 -4577695.1 22 648 -1057735.5 -4901618.8 363% 519 446s
12380 10880 -4268477.7 26 564 -1057735.5 -4891135.5 362% 520 454s
12887 10892 -4520809.0 28 568 -1057735.5 -4880134.4 361% 522 471s
H12905 10892 -1084222.389 -4877569.6 350% 523 471s
12909 11376 -4448842.0 24 580 -1084222.4 -4874848.0 350% 523 479s
13421 11925 -4543476.2 27 552 -1084222.4 -4862277.7 348% 524 487s
H13990 12509 -1085559.540 -4850356.3 347% 524 497s
H14516 12509 -1085600.895 -4846109.7 346% 524 497s
14594 13093 -4493308.6 27 532 -1085600.9 -4837330.8 346% 523 506s
15210 13755 -4674542.8 27 588 -1085600.9 -4825121.3 344% 523 515s
15900 14210 -4412059.2 27 566 -1085600.9 -4805616.2 343% 522 524s
16373 14912 -4543328.8 26 604 -1085600.9 -4794193.2 342% 521 534s
17113 15548 -4420455.5 24 607 -1085600.9 -4776989.8 340% 519 545s
17781 16273 infeasible 23 -1085600.9 -4763271.7 339% 520 556s
18548 17002 -4349774.9 30 574 -1085600.9 -4749270.0 337% 519 566s
19299 17760 -4239661.8 27 590 -1085600.9 -4735986.9 336% 520 578s
20091 18565 -4503217.0 31 571 -1085600.9 -4715690.4 334% 520 590s
20924 19418 -3986732.9 32 511 -1085600.9 -4698392.4 333% 520 605s
21827 20367 infeasible 24 -1085600.9 -4683689.7 331% 520 618s
22820 21252 infeasible 25 -1085600.9 -4668459.7 330% 518 631s
23741 22294 -4369705.9 32 555 -1085600.9 -4656664.2 329% 519 644s
24815 23220 -4451385.8 28 570 -1085600.9 -4644244.9 328% 516 658s
25777 23980 infeasible 26 -1085600.9 -4634857.9 327% 516 671s
26563 25008 -3870566.4 31 514 -1085600.9 -4624501.5 326% 516 686s
27597 26043 -4300061.5 32 539 -1085600.9 -4615116.0 325% 517 702s
28650 27064 -3960683.0 28 558 -1085600.9 -4604805.0 324% 518 718s
29699 27269 -4003957.2 32 490 -1085600.9 -4595651.4 323% 518 747s
H29786 27269 -1085600.895 -4594692.7 323% 518 747s
29908 28439 -4268801.3 25 564 -1085600.9 -4593287.9 323% 518 765s
31104 29717 -4274039.8 29 557 -1085600.9 -4581950.0 322% 518 784s
H31252 29717 -1086290.148 -4581688.2 322% 518 784s
32388 31100 -4418656.8 27 587 -1086290.1 -4572323.4 321% 517 803s
33789 32559 -4415197.5 25 602 -1086290.1 -4560192.5 320% 516 823s
35266 33980 -4335338.0 26 603 -1086290.1 -4548186.8 319% 514 844s
36699 35095 -4296234.0 26 526 -1086290.1 -4540391.3 318% 514 865s
37820 36593 -4331437.5 28 564 -1086290.1 -4532413.0 317% 515 888s
39330 38154 -3907051.0 31 498 -1086290.1 -4522676.2 316% 515 911s
40901 39906 -4351265.3 27 577 -1086290.1 -4511428.2 315% 515 935s
42657 41619 -4290846.2 26 601 -1086290.1 -4505187.0 315% 515 962s
44378 43615 -3859083.2 32 513 -1086290.1 -4490565.4 313% 515 988s
46380 45362 -3972063.9 29 517 -1086290.1 -4477273.0 312% 514 1011s
48135 47074 -4126199.8 27 594 -1086290.1 -4468783.5 311% 513 1034s
49855 48725 -4187645.9 30 558 -1086290.1 -4460352.8 311% 512 1056s
51518 50453 -4294921.3 27 548 -1086290.1 -4451204.6 310% 512 1078s
53252 52119 -4257841.5 32 541 -1086290.1 -4440322.3 309% 510 1102s
54924 53784 -4246774.5 28 544 -1086290.1 -4432996.4 308% 509 1124s
56595 55444 -3938853.4 28 527 -1086290.1 -4425213.2 307% 508 1146s
58265 57060 -4111261.5 27 572 -1086290.1 -4418127.4 307% 507 1168s
59883 58758 -3775789.9 26 533 -1086290.1 -4412048.3 306% 507 1194s
61589 60341 -4118176.3 27 574 -1086290.1 -4406666.1 306% 506 1219s
63179 62414 -4195230.4 35 526 -1086290.1 -4399476.0 305% 505 1247s
65264 64131 -4239501.5 28 544 -1086290.1 -4391098.9 304% 504 1269s
66999 65676 -3853436.1 31 506 -1086290.1 -4382915.6 303% 503 1289s
68546 66562 -4138485.2 30 583 -1086290.1 -4376444.0 303% 502 1314s
H68578 66562 -1086634.775 -4376444.0 303% 502 1314s
H69156 66562 -1086634.795 -4375660.2 303% 502 1314s
Interrupt request received
69434 66706 -3979004.9 29 560 -1086634.8 -4374920.5 303% 502 1331s
Cutting planes:
Gomory: 85
Lift-and-project: 130
Cover: 560
Implied bound: 322
Projected implied bound: 20
Clique: 573
MIR: 796
StrongCG: 44
Flow cover: 1966
GUB cover: 24
Zero half: 145
Network: 3
RLT: 231
Relax-and-lift: 1065
BQP: 5
PSD: 18
Explored 69578 nodes (34909537 simplex iterations) in 1332.02 seconds (1798.03 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: -1.08663e+06 -1.08663e+06 -1.08629e+06 ... -1.05733e+06
Solve interrupted
Best objective -1.086634794646e+06, best bound -4.372719942303e+06, gap 302.4093%
It comes that the gap narrows very slowly and after 1000s the optimal solution is not found.I've also tried the NoRelHeurTime parameter but it doesn't make much difference.Can anyone tell me the possible reasons and the corresponding improvement measures?
Thanks in advance!
0
-
Hi Suyue,
There are multiple things to consider here.
You can see the warning
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Gurobi sets very small coefficients to \(0\). If these coefficients play a significant role for the solution of your model then you might want to re-scale and/or reformulate your model. For re-scaling, please have a look at our Guidelines for Numerical Issues and for improving model formulation please have a look at our Tech Talk about strong MIP formulations.
From the log, it is not clear whether it is the best objective that should be improved or the best bound. Do you have an idea about the optimal objective value for your model?
You should update to the latest version 10.0.1 if possible.
Could you construct a smaller version of the model? This would make it way easier for you to analyze what actually makes the model so hard (and possibly finding suiting parameters). I would guess that reducing the size of the model by a factor of 10 should already be good enough to make it "analyzable by hand".
Best regards,
Jaromił0 -
Thank you for your comment!
It seems that the model has numerical issues, as the binary variables could oscilate during the branch-and-bound.Here is the possible problem syntax(written in MATLAB with yalmip):
Pw_q==Pw+zetaw_pos.*(repmat(Pw_max,1,T)-Pw)-zetaw_neg.*Pw;
This syntax aims to introduce a box uncertainty set of wind turbine power to indicate whether the output power touches the upper boundary or the lower boundary.I think the problem lies in the boundary set:when the upper boundary and lower boundary remain same(say both are 0), the binary variable(zetaw_pos and zetaw_neg) can either be 0 or 1.And that may lead to the slow descent of the gap.
And after I revised the boundary to avoid this problem,the efficient do promote a lot,as gurobi is able to get a solution in about 60s.But the solving process is somekind weird as the solution is concluedd when the gap is very big:
Removed 217 duplicated or redundant inequalities
Transfered 2476 inequalities to equalities
Set parameter Username
Set parameter MIPGap to value 0.03
Set parameter CrossoverBasis to value 0
Set parameter MIPFocus to value 3
Set parameter NodefileDir to value ""
Set parameter NoRelHeurTime to value 5
Set parameter PreSOS2BigM to value 0
Set parameter TuneTrials to value 3
Academic license - for non-commercial use only - expires 2023-12-04
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 29167 rows, 14644 columns and 409035 nonzeros
Model fingerprint: 0x51c1326d
Variable types: 8817 continuous, 5827 integer (5827 binary)
Coefficient statistics:
Matrix range [1e-03, 1e+04]
Objective range [1e+01, 1e+03]
Bounds range [1e+00, 1e+00]
RHS range [3e-14, 1e+04]
Presolve removed 25656 rows and 10950 columns
Presolve time: 0.11s
Presolved: 3511 rows, 3694 columns, 13776 nonzeros
Variable types: 1889 continuous, 1805 integer (1803 binary)
Found heuristic solution: objective -2581.451134
Starting NoRel heuristic
Found heuristic solution: objective -2581.452201
Found heuristic solution: objective -2581.452342
Elapsed time for NoRel heuristic: 6s (best bound -5.8162e+06)
Root relaxation presolve removed 936 rows and 936 columns
Root relaxation presolved: 2575 rows, 2758 columns, 11904 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -1.4283703e+07 1.533155e+04 0.000000e+00 6s
1292 -5.8162046e+06 0.000000e+00 0.000000e+00 6s
1300 -5.8162046e+06 0.000000e+00 0.000000e+00 6s
Extra simplex iterations after uncrush: 8
Root relaxation: objective -5.816205e+06, 1300 iterations, 0.03 seconds (0.06 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -5816204.6 0 396 -2581.4523 -5816204.6 - - 6s
0 0 -4667065.4 0 407 -2581.4523 -4667065.4 - - 6s
0 0 -4667065.4 0 396 -2581.4523 -4667065.4 - - 7s
0 0 -4644213.9 0 407 -2581.4523 -4644213.9 - - 7s
0 0 -4435929.5 0 420 -2581.4523 -4435929.5 - - 7s
0 0 -4434038.3 0 422 -2581.4523 -4434038.3 - - 7s
0 0 -4433861.8 0 421 -2581.4523 -4433861.8 - - 7s
0 0 -3869708.8 0 476 -2581.4523 -3869708.8 - - 8s
0 0 -3834164.1 0 484 -2581.4523 -3834164.1 - - 8s
0 0 -3584812.6 0 483 -2581.4523 -3584812.6 - - 8s
0 0 -3584812.6 0 494 -2581.4523 -3584812.6 - - 8s
0 0 -3584812.6 0 498 -2581.4523 -3584812.6 - - 8s
0 0 -3565604.2 0 458 -2581.4523 -3565604.2 - - 10s
0 0 -3426214.4 0 466 -2581.4523 -3426214.4 - - 10s
0 0 -3426214.4 0 466 -2581.4523 -3426214.4 - - 10s
0 0 -3388726.0 0 464 -2581.4523 -3388726.0 - - 12s
0 0 -3387450.6 0 480 -2581.4523 -3387450.6 - - 12s
0 0 -3387450.6 0 480 -2581.4523 -3387450.6 - - 12s
0 0 -3387450.6 0 498 -2581.4523 -3387450.6 - - 12s
0 0 -3291074.8 0 480 -2581.4523 -3291074.8 - - 13s
0 0 -3280952.8 0 468 -2581.4523 -3280952.8 - - 13s
0 0 -3280952.8 0 474 -2581.4523 -3280952.8 - - 13s
0 0 -3224916.2 0 460 -2581.4523 -3224916.2 - - 15s
0 0 -3219546.1 0 476 -2581.4523 -3219546.1 - - 15s
0 0 -3219546.1 0 480 -2581.4523 -3219546.1 - - 15s
0 0 -3189232.9 0 482 -2581.4523 -3189232.9 - - 17s
0 0 -3142551.3 0 500 -2581.4523 -3142551.3 - - 17s
0 0 -3116673.0 0 498 -2581.4523 -3116673.0 - - 17s
0 0 -3116673.0 0 504 -2581.4523 -3116673.0 - - 17s
0 0 -3116673.0 0 512 -2581.4523 -3116673.0 - - 17s
0 0 -3104159.6 0 513 -2581.4523 -3104159.6 - - 18s
0 0 -2972930.7 0 442 -2581.4523 -2972930.7 - - 19s
0 2 -2972930.7 0 437 -2581.4523 -2972930.7 - - 19s
3 8 -2671571.3 2 429 -2581.4523 -2879395.7 - 290 20s
H 211 125 -2581.543570 -2167624.8 - 248 24s
310 181 -2121977.3 12 354 -2581.5436 -2131973.4 - 221 25s
1145 859 infeasible 19 -2581.5436 -1974983.3 - 173 30s
1467 1051 -1697276.1 18 313 -2581.5436 -1702983.2 - 165 36s
1476 1057 -1322251.6 13 322 -2581.5436 -1322251.6 - 164 41s
1484 1062 -1191543.2 12 328 -2581.5436 -1191543.2 - 163 45s
1503 1076 -1083075.8 8 323 -2581.5436 -1083075.8 - 169 50s
1517 1085 -723153.77 18 337 -2581.5436 -723153.77 - 168 55s
1530 1094 -88330.910 21 279 -2581.5436 -88330.910 3322% 166 60s
1538 1097 -28053.295 29 218 -2581.5436 -28053.295 987% 175 65s
Cutting planes:
Learned: 1
Gomory: 13
Lift-and-project: 89
Cover: 131
Implied bound: 32
Clique: 26
MIR: 123
StrongCG: 4
Flow cover: 250
GUB cover: 17
Inf proof: 3
Zero half: 12
Network: 1
RLT: 4
Relax-and-lift: 14
BQP: 2
Explored 1707 nodes (290334 simplex iterations) in 66.55 seconds (67.93 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: -2581.54 -2581.54 -2581.45 ... -2581.45
No other solutions better than -2581.54
Optimal solution found (tolerance 3.00e-02)
Best objective -2.581543575333e+03, best bound -2.581543575333e+03, gap 0.0000%I'm wondering if there is still some numeric issues since the gap suddenly steps from 987% to 0.And by the way, the size of the model can't be reduced anymore since I have to construct the kkt condition of the model,which means I need to introduce a lot binaries to slack the complementary condition.
0 -
I'm wondering if there is still some numeric issues since the gap suddenly steps from 987% to 0.
While quite rare, it is not unusual behavior, especially for more complex models. It is possible that a heuristic or a B&B dive finds some information which allows to prune a big chunk of the tree resulting in big MIPGap jumps.
You can see that the No Relaxation Heuristic found a very good solution very quickly. This can lead to impactful presolve reductions which ultimately lead to quicker convergence.
You should definitely check whether the solution computed by Gurobi satisfies the needs of your application.
The RHS range of your constraints is questionable
RHS range [3e-14, 1e+04]
It would be best to clean it up manually before optimizing and set very small coefficients to \(0\) or re-scale the model as suggested in my previous comment.
The same applies regarding the Warning
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
And at least, you have the option to update to v10 to profit from performance improvements and bug fixes.
0 -
Thank you, Jaromil
I will try to clean up very small coefficients and pay attention to the numeric issues.Thank you for your kindly comment again!
0 -
Hi Jaromil
Unfortunately the MILP model can find a solution in less than 10 min,but i'm still not satisfied with the efficiency.After I revised problems you mentioned above, it seems that the heuristics model find the solution from the beginning but it struggles to find the best bound.Here is the log:
Set parameter Username
Set parameter MIPGap to value 0.01
Set parameter CrossoverBasis to value 0
Set parameter MIPFocus to value 3
Set parameter NodefileDir to value ""
Set parameter NoRelHeurTime to value 20
Set parameter Cuts to value 3
Set parameter PreSOS2BigM to value 0
Set parameter TuneTrials to value 3
Academic license - for non-commercial use only - expires 2024-06-06
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 33808 rows, 14585 columns and 315796 nonzeros
Model fingerprint: 0x73e9d9e9
Variable types: 8130 continuous, 6455 integer (6455 binary)
Coefficient statistics:
Matrix range [3e-04, 1e+04]
Objective range [3e-01, 2e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 1e+04]
Presolve removed 29486 rows and 10511 columns
Presolve time: 0.41s
Presolved: 4322 rows, 4074 columns, 14508 nonzeros
Variable types: 2510 continuous, 1564 integer (1564 binary)
Starting NoRel heuristic
Found phase-1 solution: relaxation 34839.7
Found phase-1 solution: relaxation 34825.8
Found phase-1 solution: relaxation 34536.8
Found phase-1 solution: relaxation 34473.5
Found phase-1 solution: relaxation 7818.41
Found phase-1 solution: relaxation 7461.44
Found phase-1 solution: relaxation 6905.05
Found phase-1 solution: relaxation 6068.39
Found phase-1 solution: relaxation 5208.38
Found phase-1 solution: relaxation 2641.62
Found phase-1 solution: relaxation 2615.4
Found phase-1 solution: relaxation 2246.63
Found phase-1 solution: relaxation 1988.52
Found phase-1 solution: relaxation 1772.27
Found phase-1 solution: relaxation 1718.13
Found phase-1 solution: relaxation 1564.16
Found phase-1 solution: relaxation 1451.22
Found phase-1 solution: relaxation 1451.21
Found phase-1 solution: relaxation 1450.87
Found phase-1 solution: relaxation 1449.03
Found phase-1 solution: relaxation 1449.01
Found phase-1 solution: relaxation 1355.37
Found phase-1 solution: relaxation 1292.59
Found phase-1 solution: relaxation 1255.96
Found phase-1 solution: relaxation 1252.97
Found phase-1 solution: relaxation 1219.44
Found phase-1 solution: relaxation 1057.55
Found phase-1 solution: relaxation 954.437
Found phase-1 solution: relaxation 937.607
Found phase-1 solution: relaxation 880.965
Found phase-1 solution: relaxation 814.701
Found phase-1 solution: relaxation 807.84
Found phase-1 solution: relaxation 799.182
Found phase-1 solution: relaxation 765.258
Found phase-1 solution: relaxation 704.463
Found phase-1 solution: relaxation 680.014
Found phase-1 solution: relaxation 676.414
Found phase-1 solution: relaxation 645.723
Found phase-1 solution: relaxation 645.72
Found phase-1 solution: relaxation 642.346
Found phase-1 solution: relaxation 629.765
Found phase-1 solution: relaxation 616.697
Found phase-1 solution: relaxation 604.417
Found phase-1 solution: relaxation 600.956
Found phase-1 solution: relaxation 578.192
Found phase-1 solution: relaxation 574.722
Found phase-1 solution: relaxation 574.717
Found phase-1 solution: relaxation 502.014
Found phase-1 solution: relaxation 501.626
Found phase-1 solution: relaxation 493.187
Found phase-1 solution: relaxation 493.184
Found phase-1 solution: relaxation 473.362
Found phase-1 solution: relaxation 473.076
Found phase-1 solution: relaxation 473.075
Found phase-1 solution: relaxation 472.934
Found phase-1 solution: relaxation 472.647
Found phase-1 solution: relaxation 462.699
Found phase-1 solution: relaxation 462.695
Found phase-1 solution: relaxation 439.008
Found phase-1 solution: relaxation 436.682
Found phase-1 solution: relaxation 320.432
Found phase-1 solution: relaxation 318.201
Found phase-1 solution: relaxation 313.778
Found phase-1 solution: relaxation 313.19
Found phase-1 solution: relaxation 313.073
Found phase-1 solution: relaxation 312.901
Found phase-1 solution: relaxation 311.792
Found phase-1 solution: relaxation 308.126
Found phase-1 solution: relaxation 285.554
Found phase-1 solution: relaxation 279.175
Found phase-1 solution: relaxation 278.367
Found phase-1 solution: relaxation 271.357
Found phase-1 solution: relaxation 229.721
Found phase-1 solution: relaxation 131.886
Found phase-1 solution: relaxation 108.55
Found phase-1 solution: relaxation 108.537
Found phase-1 solution: relaxation 108.221
Found phase-1 solution: relaxation 108.22
Found phase-1 solution: relaxation 108.207
Found phase-1 solution: relaxation 108.207
Found phase-1 solution: relaxation 107.663
Found phase-1 solution: relaxation 86.6035
Found phase-1 solution: relaxation 86.2127
Found phase-1 solution: relaxation 83.6826
Found phase-1 solution: relaxation 81.1013
Found phase-1 solution: relaxation 77.1161
Found phase-1 solution: relaxation 72.7764
Found phase-1 solution: relaxation 68.3536
Found phase-1 solution: relaxation 67.9194
Found phase-1 solution: relaxation 64.1304
Found phase-1 solution: relaxation 58.6391
Found phase-1 solution: relaxation 58.1782
Found phase-1 solution: relaxation 51.0738
Found phase-1 solution: relaxation 50.327
Found phase-1 solution: relaxation 47.7701
Found phase-1 solution: relaxation 47.7316
Found phase-1 solution: relaxation 47.4314
Found phase-1 solution: relaxation 46.3485
Found phase-1 solution: relaxation 45.761
Found phase-1 solution: relaxation 42.9752
Found phase-1 solution: relaxation 42.867
Found phase-1 solution: relaxation 42.705
Found phase-1 solution: relaxation 42.6603
Found phase-1 solution: relaxation 42.4227
Found phase-1 solution: relaxation 42.3405
Found phase-1 solution: relaxation 36.7601
Found phase-1 solution: relaxation 34.053
Found phase-1 solution: relaxation 0
Found heuristic solution: objective -2071.378493
Transition to phase 2
Found heuristic solution: objective -4318.593812
Found heuristic solution: objective -6168.785979
Found heuristic solution: objective -6248.871868
Found heuristic solution: objective -6963.104062
Found heuristic solution: objective -7138.650896
Found heuristic solution: objective -8039.967780
Found heuristic solution: objective -10902.59250
Found heuristic solution: objective -12139.52933
Found heuristic solution: objective -12219.61522
Found heuristic solution: objective -15226.24593
Found heuristic solution: objective -15241.18757
Found heuristic solution: objective -16367.48261
Found heuristic solution: objective -19389.05496
Found heuristic solution: objective -21158.74883
Found heuristic solution: objective -21353.13808
Found heuristic solution: objective -22494.49922
Found heuristic solution: objective -22814.05203
Elapsed time for NoRel heuristic: 5s (best bound -85144.4)
Found heuristic solution: objective -23036.66308
Found heuristic solution: objective -23375.82982
Found heuristic solution: objective -23375.82983
Found heuristic solution: objective -23375.82985
Elapsed time for NoRel heuristic: 10s (best bound -85144.4)
Found heuristic solution: objective -23375.82986
Elapsed time for NoRel heuristic: 15s (best bound -85144.4)
Found heuristic solution: objective -23375.82986
Elapsed time for NoRel heuristic: 22s (best bound -85144.4)
Root relaxation presolve removed 1509 rows and 1509 columns
Root relaxation presolved: 2813 rows, 2565 columns, 11488 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -7.4861268e+05 4.108696e+06 0.000000e+00 22s
1641 -8.5144387e+04 0.000000e+00 0.000000e+00 22s
1673 -8.5144387e+04 0.000000e+00 0.000000e+00 22s
Extra simplex iterations after uncrush: 32
Root relaxation: objective -8.514439e+04, 1673 iterations, 0.06 seconds (0.05 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -85144.387 0 590 -23375.830 -85144.387 264% - 23s
0 0 -54204.462 0 785 -23375.830 -54204.462 132% - 25s
0 0 -54204.462 0 781 -23375.830 -54204.462 132% - 25s
0 0 -51715.194 0 753 -23375.830 -51715.194 121% - 25s
0 0 -51715.194 0 753 -23375.830 -51715.194 121% - 25s
0 0 -51713.960 0 738 -23375.830 -51713.960 121% - 25s
0 0 -51713.960 0 763 -23375.830 -51713.960 121% - 25s
0 0 -51571.622 0 737 -23375.830 -51571.622 121% - 25s
0 0 -51571.622 0 762 -23375.830 -51571.622 121% - 25s
0 0 -51571.622 0 765 -23375.830 -51571.622 121% - 25s
0 0 -49984.710 0 794 -23375.830 -49984.710 114% - 27s
0 0 -48896.257 0 802 -23375.830 -48896.257 109% - 28s
0 0 -48525.927 0 718 -23375.830 -48525.927 108% - 30s
0 0 -48525.927 0 721 -23375.830 -48525.927 108% - 30s
0 0 -46779.528 0 674 -23375.830 -46779.528 100% - 30s
0 0 -46779.409 0 671 -23375.830 -46779.409 100% - 30s
0 0 -46612.486 0 693 -23375.830 -46612.486 99.4% - 30s
0 0 -46576.799 0 710 -23375.830 -46576.799 99.3% - 30s
0 0 -45061.350 0 673 -23375.830 -45061.350 92.8% - 33s
0 0 -45051.543 0 691 -23375.830 -45051.543 92.7% - 33s
0 0 -44832.460 0 677 -23375.830 -44832.460 91.8% - 35s
0 0 -44832.460 0 677 -23375.830 -44832.460 91.8% - 37s
0 0 -44832.460 0 464 -23375.830 -44832.460 91.8% - 38s
0 0 -44832.460 0 568 -23375.830 -44832.460 91.8% - 39s
H 0 0 -23375.82990 -44832.460 91.8% - 39s
0 0 -44832.460 0 547 -23375.830 -44832.460 91.8% - 39s
0 0 -44832.460 0 481 -23375.830 -44832.460 91.8% - 39s
0 0 -44832.460 0 454 -23375.830 -44832.460 91.8% - 39s
0 0 -44832.460 0 417 -23375.830 -44832.460 91.8% - 39s
0 0 -44832.460 0 422 -23375.830 -44832.460 91.8% - 39s
0 0 -44832.460 0 422 -23375.830 -44832.460 91.8% - 39s
0 0 -44475.327 0 486 -23375.830 -44475.327 90.3% - 41s
0 0 -43343.206 0 490 -23375.830 -43343.206 85.4% - 41s
0 0 -43343.206 0 472 -23375.830 -43343.206 85.4% - 41s
0 0 -42622.193 0 495 -23375.830 -42622.193 82.3% - 43s
0 0 -42113.386 0 513 -23375.830 -42113.386 80.2% - 43s
0 0 -42113.386 0 603 -23375.830 -42113.386 80.2% - 43s
0 0 -42062.210 0 604 -23375.830 -42062.210 79.9% - 43s
0 0 -41097.172 0 600 -23375.830 -41097.172 75.8% - 44s
0 0 -41097.172 0 600 -23375.830 -41097.172 75.8% - 44s
0 0 -40946.632 0 587 -23375.830 -40946.632 75.2% - 44s
0 0 -40660.983 0 590 -23375.830 -40660.983 73.9% - 45s
0 0 -40660.983 0 593 -23375.830 -40660.983 73.9% - 45s
0 0 -40579.997 0 619 -23375.830 -40579.997 73.6% - 45s
0 0 -40579.997 0 628 -23375.830 -40579.997 73.6% - 45s
H 0 0 -23375.82994 -40560.103 73.5% - 46s
0 0 -40058.088 0 595 -23375.830 -40058.088 71.4% - 46s
0 0 -39940.870 0 607 -23375.830 -39940.870 70.9% - 46s
0 0 -39836.725 0 617 -23375.830 -39836.725 70.4% - 46s
0 0 -39667.372 0 596 -23375.830 -39667.372 69.7% - 47s
0 0 -39604.819 0 602 -23375.830 -39604.819 69.4% - 47s
0 0 -39351.534 0 579 -23375.830 -39351.534 68.3% - 48s
0 0 -39189.161 0 619 -23375.830 -39189.161 67.6% - 48s
0 0 -39014.825 0 640 -23375.830 -39014.825 66.9% - 48s
0 0 -39014.825 0 640 -23375.830 -39014.825 66.9% - 48s
0 0 -38944.425 0 631 -23375.830 -38944.425 66.6% - 49s
0 0 -38887.376 0 630 -23375.830 -38887.376 66.4% - 50s
0 2 -38887.376 0 630 -23375.830 -38887.376 66.4% - 51s
57 49 infeasible 9 -23375.830 -38285.425 63.8% 1216 55s
207 166 -37151.344 14 462 -23375.830 -37151.344 58.9% 827 60s
366 329 -35780.082 18 324 -23375.830 -36641.835 56.8% 658 65s
908 774 -35073.179 13 496 -23375.830 -36205.118 54.9% 468 70s
H 920 774 -23375.82999 -36193.893 54.8% 468 70s
1359 1182 -35345.520 16 364 -23375.830 -35781.545 53.1% 454 75s
1480 1185 -35620.140 20 443 -23375.830 -35732.148 52.9% 440 81s
1492 1193 -33575.356 18 558 -23375.830 -35732.148 52.9% 437 89s
1498 1197 -33230.431 22 565 -23375.830 -35732.148 52.9% 435 91s
1499 1198 -30087.971 13 528 -23375.830 -35732.148 52.9% 435 95s
1504 1201 -33219.850 22 538 -23375.830 -35732.148 52.9% 433 102s
1510 1205 -32609.905 27 577 -23375.830 -34912.325 49.4% 432 105s
1517 1210 -34346.471 14 554 -23375.830 -34346.471 46.9% 430 110s
1521 1212 -33896.066 17 529 -23375.830 -33896.066 45.0% 429 115s
1524 1214 -33759.697 17 576 -23375.830 -33759.697 44.4% 428 121s
1530 1218 -33174.026 18 527 -23375.830 -33174.026 41.9% 426 127s
1534 1221 -28235.239 16 545 -23375.830 -32660.098 39.7% 425 133s
1538 1224 -32471.002 23 545 -23375.830 -32471.002 38.9% 424 135s
1543 1227 -31821.621 15 567 -23375.830 -31821.621 36.1% 422 142s
1547 1230 -31660.990 19 530 -23375.830 -31660.990 35.4% 421 147s
1552 1233 -31369.953 14 523 -23375.830 -31369.953 34.2% 420 150s
1557 1236 -31285.659 16 515 -23375.830 -31285.659 33.8% 419 155s
1565 1242 -30641.469 20 555 -23375.830 -30776.959 31.7% 417 161s
1566 1242 -30734.749 26 546 -23375.830 -30734.749 31.5% 416 165s
1576 1249 -30562.352 16 547 -23375.830 -30562.352 30.7% 414 170s
1580 1252 -30365.167 20 534 -23375.830 -30365.167 29.9% 413 176s
1587 1256 -30173.546 22 572 -23375.830 -30173.546 29.1% 411 180s
1593 1260 -30128.904 20 564 -23375.830 -30128.904 28.9% 409 185s
1601 1266 -30037.731 21 502 -23375.830 -30037.731 28.5% 407 191s
1610 1272 -29814.656 27 519 -23375.830 -29814.656 27.5% 405 195s
1615 1275 -29633.881 14 518 -23375.830 -29633.881 26.8% 404 200s
1621 1280 -29633.881 17 379 -23375.830 -29633.881 26.8% 464 205s
1632 1287 -29633.881 21 486 -23375.830 -29633.881 26.8% 461 210s
1638 1291 -29633.881 23 503 -23375.830 -29633.881 26.8% 459 216s
1640 1293 -29633.881 17 515 -23375.830 -29633.881 26.8% 458 221s
1645 1296 -29633.881 21 499 -23375.830 -29633.881 26.8% 457 228s
1648 1298 -29633.881 17 522 -23375.830 -29633.881 26.8% 456 231s
1650 1299 -29633.881 21 504 -23375.830 -29633.881 26.8% 456 235s
1654 1302 -29633.881 22 518 -23375.830 -29633.881 26.8% 454 240s
1661 1307 -29633.881 20 510 -23375.830 -29633.881 26.8% 453 246s
1663 1308 -29633.881 22 493 -23375.830 -29633.881 26.8% 452 263s
1667 1312 -29633.881 18 392 -23375.830 -29633.881 26.8% 472 265s
1678 1320 -29633.881 16 489 -23375.830 -29633.881 26.8% 469 271s
1680 1321 -29633.881 20 493 -23375.830 -29633.881 26.8% 468 275s
1683 1323 -29633.881 14 490 -23375.830 -29633.881 26.8% 468 302s
1687 1327 -29633.881 41 390 -23375.830 -29633.881 26.8% 479 305s
1749 1340 -29633.881 47 391 -23375.830 -29633.881 26.8% 506 310s
1813 1364 -29633.881 51 351 -23375.830 -29633.881 26.8% 533 315s
1878 1389 -29199.202 53 316 -23375.830 -29633.881 26.8% 568 320s
1929 1411 -29011.725 54 351 -23375.830 -29225.418 25.0% 589 325s
2023 1462 -26982.495 53 302 -23375.830 -28469.300 21.8% 619 330s
2157 1499 -24067.149 56 283 -23375.830 -27846.488 19.1% 640 336s
2273 1504 -25726.303 55 310 -23375.830 -27432.426 17.4% 669 341s
H 2308 1429 -23375.83000 -27298.528 16.8% 680 344s
2319 1435 -25933.386 57 294 -23375.830 -27270.183 16.7% 686 346s
2483 1389 -26170.034 56 275 -23375.830 -26773.903 14.5% 710 351s
2694 1326 cutoff 55 -23375.830 -26164.120 11.9% 730 356s
2871 1254 -24862.156 61 237 -23375.830 -25764.787 10.2% 732 360s
3172 1102 infeasible 62 -23375.830 -25025.324 7.06% 729 367s
3311 1017 cutoff 60 -23375.830 -24614.620 5.30% 726 371s
3672 833 cutoff 65 -23375.830 -23989.853 2.63% 699 375s
Cutting planes:
Learned: 1
Gomory: 4
Lift-and-project: 115
Cover: 506
Implied bound: 508
Projected implied bound: 10
Clique: 1679
MIR: 876
StrongCG: 8
Flow cover: 2199
Zero half: 87
Network: 6
RLT: 489
Relax-and-lift: 402
BQP: 74
PSD: 14
Explored 3983 nodes (2705378 simplex iterations) in 377.83 seconds (467.16 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: -23375.8 -23375.8 -23375.8 ... -23036.7
Optimal solution found (tolerance 1.00e-02)
Best objective -2.337583000142e+04, best bound -2.355547955495e+04, gap 0.7685%Before the reformulation of the model,is there any possible way to improve the best bound?What' more,the log ends with arrays of 'infeasible' and 'cutoff',is this message indicate why the model moves very slow?
Thanks in advance!
0 -
Before the reformulation of the model,is there any possible way to improve the best bound?
You could try combinations of the following parameters:
- PreSparsify = 0 / 1
- MIPFocus = 2 / 3
- Presolve = -1 / 1 / 2
- Cuts = 2 / 3
- Set CrossoverBasis to its default value
- Set PreSOS2BigM to its default value
Is there a particular reason why you set PreSOS2BigM?
What' more, the log ends with arrays of 'infeasible' and 'cutoff', is this message indicate why the model moves very slow?
These are actually good messages. This means that the current node has been cutoff or that it is infeasible. This leads to a smaller tree which is good.
If nothing of this helps, I think that the last resort would be a stronger formulation. Maybe our Tech Talk on converting weak to strong MIP formulation is helpful.
0
Please sign in to leave a comment.
Comments
6 comments