Decision Optimization

 View Only
  • 1.  MIP Performance improvement

    Posted Mon November 29, 2021 10:47 PM
    Dear CPLEX Experts,
    Any suggestions on how can I improve run time by looking at the below CPLEX log. Log file has been attached for better readability.
    Cplex version : 12.9

    Tried aggregator 5 times.
    MIP Presolve eliminated 2690375 rows and 2582107 columns.
    MIP Presolve modified 12845 coefficients.
    Aggregator did 511302 substitutions.
    Reduced MIP has 156072 rows, 304655 columns, and 999212 nonzeros.
    Reduced MIP has 1326 binaries, 914 generals, 0 SOSs, and 0 indicators.
    Presolve time = 18.27 sec. (8651.00 ticks)
    Probing fixed 31 vars, tightened 2370 bounds.
    Probing time = 0.31 sec. (38.13 ticks)
    Tried aggregator 3 times.
    MIP Presolve eliminated 21805 rows and 47522 columns.
    MIP Presolve modified 895 coefficients.
    Aggregator did 127 substitutions.
    Reduced MIP has 134140 rows, 257006 columns, and 861231 nonzeros.
    Reduced MIP has 1273 binaries, 1001 generals, 0 SOSs, and 0 indicators.
    Presolve time = 5.27 sec. (1848.75 ticks)
    Probing fixed 0 vars, tightened 150 bounds.
    Probing time = 0.45 sec. (28.28 ticks)
    Tried aggregator 1 time.
    MIP Presolve modified 55 coefficients.
    Reduced MIP has 134140 rows, 257006 columns, and 861231 nonzeros.
    Reduced MIP has 1273 binaries, 1001 generals, 0 SOSs, and 0 indicators.
    Presolve time = 1.14 sec. (388.78 ticks)
    Probing fixed 0 vars, tightened 1 bounds.
    Probing time = 0.17 sec. (21.49 ticks)
    Clique table members: 196.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 8 threads.
    Root relaxation solution time = 29.36 sec. (11892.21 ticks)

    Nodes Cuts/
    Node Left Objective IInf Best Integer Best Bound ItCnt Gap

    0 0 431875.9719 773 431875.9719 38504
    0 0 433953.1517 476 Cuts: 2532 41754
    * 0+ 0 2.10329e+008 433953.1517 43385 99.79%
    0 0 435469.2359 441 2.10329e+008 Cuts: 860 43385 99.79%
    0 0 435758.1705 434 2.10329e+008 Cuts: 560 44295 99.79%
    0 0 436063.0213 402 2.10329e+008 Cuts: 212 44733 99.79%
    0 0 436216.8339 350 2.10329e+008 Cuts: 416 45244 99.79%
    0 0 436360.2849 352 2.10329e+008 Cuts: 107 45478 99.79%
    0 0 436573.9469 331 2.10329e+008 Cuts: 111 45888 99.79%
    0 0 436589.4654 345 2.10329e+008 Cuts: 96 46014 99.79%
    0 0 436590.8445 348 2.10329e+008 Cuts: 36 46057 99.79%
    0 2 436590.8445 348 2.10329e+008 436590.8445 46057 99.79%
    Elapsed time = 155.48 sec. (82181.02 ticks, tree = 0.01 MB, solutions = 1)
    2 4 436663.8692 360 2.10329e+008 436590.8445 46450 99.79%
    4 6 436840.7230 361 2.10329e+008 436638.0164 46715 99.79%
    9 11 436999.3365 331 2.10329e+008 436638.0164 47229 99.79%
    14 16 436748.6914 349 2.10329e+008 436698.7542 47632 99.79%
    31 33 437571.0261 339 2.10329e+008 436698.7542 49220 99.79%
    43 45 438418.0875 328 2.10329e+008 436698.7542 50487 99.79%
    49 51 438028.3138 272 2.10329e+008 436698.7542 51095 99.79%
    65 67 438030.1374 266 2.10329e+008 436698.7542 53067 99.79%
    75 77 437872.6805 299 2.10329e+008 436698.7542 53831 99.79%
    121 122 438226.6209 308 2.10329e+008 436698.7542 58753 99.79%
    Elapsed time = 164.80 sec. (86994.52 ticks, tree = 1.17 MB, solutions = 1)
    * 177+ 174 451744.3808 436698.7542 62131 3.33%
    177 176 437940.1292 284 451744.3808 436698.7542 62131 3.33%
    331 323 441593.1897 255 451744.3808 436698.7542 70052 3.33%
    456 445 444088.0897 204 451744.3808 436698.7542 84563 3.33%
    482 471 441050.4738 223 451744.3808 436698.7542 112426 3.33%
    523 511 440395.4180 221 451744.3808 436698.7542 148572 3.33%
    545 533 439033.7963 177 451744.3808 436698.7542 158516 3.33%
    569 556 440450.3810 188 451744.3808 436698.7542 177522 3.33%
    578 565 439757.1900 181 451744.3808 436698.7542 179114 3.33%
    636 623 444434.4124 169 451744.3808 436698.7542 184038 3.33%
    666 653 441409.8468 211 451744.3808 436698.7542 191243 3.33%
    Elapsed time = 206.33 sec. (107650.94 ticks, tree = 72.02 MB, solutions = 2)
    669 656 444434.4124 167 451744.3808 436698.7542 191285 3.33%
    675 662 439899.8759 191 451744.3808 436698.7542 191386 3.33%
    880 866 449150.4332 134 451744.3808 436698.7542 205660 3.33%
    926 910 439957.4890 145 451744.3808 436698.7542 209259 3.33%
    1054 1033 440105.1131 132 451744.3808 436698.7542 213938 3.33%
    1241 1211 442949.9829 72 451744.3808 436698.7542 226919 3.33%
    1320 1288 446764.5906 34 451744.3808 436698.7542 231028 3.33%
    1405 1372 441893.2301 116 451744.3808 436698.7542 234452 3.33%
    1501 1467 440671.6353 58 451744.3808 436698.7542 236712 3.33%
    * 1531 1477 integral 0 440656.1590 436698.7542 237734 0.90%
    Elapsed time = 228.20 sec. (118298.50 ticks, tree = 117.57 MB, solutions = 2)
    1639 1569 437123.8525 338 440656.1590 436698.7542 244487 0.90%
    1777 684 437270.5231 296 440656.1590 436698.7542 252999 0.90%
    1805 712 437140.9784 252 440656.1590 436698.7542 260726 0.90%
    1834 741 437898.2864 245 440656.1590 436797.7015 312458 0.88%
    1851 756 437866.0510 234 440656.1590 436797.7015 325207 0.88%
    1865 766 437444.0800 241 440656.1590 436797.7015 357262 0.88%
    1867 768 437917.7278 234 440656.1590 436797.7015 383365 0.88%
    1893 794 437354.2328 245 440656.1590 436797.7015 418634 0.88%
    1900 801 437476.3622 256 440656.1590 436797.7015 428548 0.88%
    1901 802 437368.3588 240 440656.1590 436797.7015 438943 0.88%
    Elapsed time = 285.44 sec. (142857.46 ticks, tree = 33.82 MB, solutions = 7)
    2011 910 437370.8486 237 440656.1590 436797.7015 500594 0.88%
    2015 914 437531.5187 211 440656.1590 436797.7015 504781 0.88%
    2032 929 437961.9539 177 440656.1590 436797.7015 515737 0.88%
    2056 953 437968.2262 170 440656.1590 436797.7015 524945 0.88%
    * 2108+ 1003 440408.5987 436797.7015 534479 0.82%
    * 2108+ 1003 440277.7544 436797.7015 534479 0.79%
    2108 1005 438847.9958 112 440277.7544 436797.7015 534479 0.79%
    * 2147+ 1040 440277.7544 436797.7015 535230 0.79%
    2147 1042 438523.4557 136 440277.7544 436797.7015 535230 0.79%
    2340 1094 438327.1366 157 440277.7544 436797.7015 548323 0.79%
    2371 1118 437114.0473 277 440277.7544 436797.7015 557243 0.79%
    2427 1170 437245.1000 262 440277.7544 436797.7015 578111 0.79%
    2455 1192 437246.2097 250 440277.7544 436797.7015 596447 0.79%
    Elapsed time = 364.02 sec. (180091.09 ticks, tree = 53.07 MB, solutions = 7)
    2476 1209 437313.9202 237 440277.7544 436797.7015 620301 0.79%
    2581 1295 437961.4002 231 440277.7544 436891.7482 701485 0.77%
    2589 1303 437961.7784 226 440277.7544 436891.7482 707595 0.77%
    2608 1320 437535.7662 232 440277.7544 436891.7482 728660 0.77%
    2631 1342 437679.0562 231 440277.7544 436891.7482 745996 0.77%
    2633 1344 437409.3851 259 440277.7544 436891.7482 758182 0.77%
    2641 1352 437420.5830 253 440277.7544 436891.7482 771206 0.77%
    2790 1482 438728.6320 223 440277.7544 436891.7482 834570 0.77%
    2803 1495 437477.8127 244 440277.7544 436891.7482 841051 0.77%
    2808 1500 437005.7159 253 440277.7544 436891.7482 856779 0.77%
    Elapsed time = 414.27 sec. (199373.18 ticks, tree = 79.12 MB, solutions = 9)
    2824 1514 436980.7571 250 440277.7544 436891.7482 860855 0.77%
    2840 1530 436999.0001 249 440277.7544 436891.7482 866860 0.77%
    2848 1538 437032.9007 248 440277.7544 436891.7482 870186 0.77%
    3024 1697 436952.8718 264 440277.7544 436891.7482 924981 0.77%
    3093 1764 438322.0017 333 440277.7544 436891.7482 930687 0.77%
    3165 1824 437920.1294 297 440277.7544 436897.4540 978284 0.77%
    3173 1832 437923.2478 295 440277.7544 436897.4540 984125 0.77%
    3181 1840 437939.9337 290 440277.7544 436897.4540 992680 0.77%
    3189 1848 437944.9222 284 440277.7544 436897.4540 1003698 0.77%
    3197 1856 437947.4149 282 440277.7544 436897.4540 1013206 0.77%
    Elapsed time = 451.30 sec. (217129.71 ticks, tree = 102.03 MB, solutions = 9)
    3216 1875 437432.0887 260 440277.7544 436897.4540 1023014 0.77%
    3252 1908 437957.0420 253 440277.7544 436897.4540 1035176 0.77%
    3260 1916 437987.7015 252 440277.7544 436897.4540 1042807 0.77%
    3284 1940 437096.4557 258 440277.7544 436897.4540 1100381 0.77%
    3410 2066 437729.9416 184 440277.7544 436897.4540 1184538 0.77%
    * 3436+ 1392 439568.4150 436897.9546 1228217 0.61%
    * 3436+ 928 439536.4059 437708.1557 1230805 0.42%
    * 3436+ 618 439249.5511 437970.9353 1235207 0.29%
    3436 619 438050.3113 319 439249.5511 438050.3113 1235411 0.27%
    3437 619 438065.3811 311 439249.5511 438050.3113 1235430 0.27%
    3438 620 438076.4242 313 439249.5511 438058.7965 1235467 0.27%
    3439 620 438148.9415 384 439249.5511 438058.7965 1235575 0.27%
    3440 620 438199.1138 307 439249.5511 438058.7965 1235682 0.27%
    Elapsed time = 838.45 sec. (507448.24 ticks, tree = 52.40 MB, solutions = 12)
    3441 621 438123.9270 314 439249.5511 438077.8961 1235940 0.27%
    3442 622 438213.0398 314 439249.5511 438077.8961 1235985 0.27%
    3446 553 438876.3428 359 439249.5511 438077.8961 1236361 0.27%
    3447 553 438884.6089 357 439249.5511 438077.8961 1236374 0.27%
    3448 553 438171.2658 375 439249.5511 438080.2699 1236512 0.27%
    3453 452 438207.7517 351 439249.5511 438080.2699 1236853 0.27%
    3454 452 438266.5809 365 439249.5511 438080.2699 1236976 0.27%
    3459 454 438473.0611 317 439249.5511 438080.2699 1237459 0.27%
    3461 455 438271.3350 307 439249.5511 438080.2699 1237512 0.27%
    3464 455 438550.4325 342 439249.5511 438080.2699 1237790 0.27%
    Elapsed time = 866.11 sec. (528766.77 ticks, tree = 37.37 MB, solutions = 12)
    3469 456 438298.2567 309 439249.5511 438080.2699 1238248 0.27%
    3477 459 438549.4645 373 439249.5511 438080.2699 1238650 0.27%
    3485 462 438306.2863 304 439249.5511 438080.2699 1239852 0.27%
    3540 431 438976.7316 350 439249.5511 438080.2699 1243285 0.27%
    3546 427 438434.1978 337 439249.5511 438080.2699 1243753 0.27%
    3602 397 438465.8833 204 439249.5511 438080.2699 1257411 0.27%
    3637 405 438808.9521 271 439249.5511 438080.2699 1259278 0.27%
    3644 407 438742.5352 287 439249.5511 438080.2699 1260057 0.27%
    3652 410 438365.4496 249 439249.5511 438080.2699 1269102 0.27%
    3701 441 438571.3831 216 439249.5511 438080.2699 1319808 0.27%
    Elapsed time = 916.13 sec. (555661.30 ticks, tree = 23.15 MB, solutions = 12)
    3751 453 438744.4935 383 439249.5511 438080.2699 1324122 0.27%
    3886 505 438655.2498 332 439249.5511 438080.2699 1335255 0.27%
    3918 514 438702.6677 247 439249.5511 438080.2699 1347731 0.27%
    4055 510 438570.8644 322 439249.5511 438080.2699 1371291 0.27%
    4075 520 438730.2215 219 439249.5511 438080.2699 1383233 0.27%
    * 4139+ 530 439244.7361 438080.2699 1407219 0.27%
    4139 532 438685.4637 207 439244.7361 438080.2699 1407219 0.27%
    4390 711 439197.8489 73 439244.7361 438080.2699 1433464 0.27%
    4533 796 438869.2326 177 439244.7361 438080.2699 1472346 0.27%
    4616 848 438666.2801 222 439244.7361 438080.2699 1527407 0.27%
    4630 857 439216.5327 56 439244.7361 438080.2699 1538055 0.27%
    Elapsed time = 1048.73 sec. (624954.25 ticks, tree = 46.97 MB, solutions = 13)
    4633 859 438424.1871 243 439244.7361 438080.2699 1550605 0.27%
    4714 923 438433.9827 186 439244.7361 438080.2699 1566520 0.27%
    * 4755+ 944 439201.9718 438080.2699 1568777 0.26%
    * 4822+ 987 439201.9401 438080.2699 1594328 0.26%
    4883 953 438179.4739 333 439201.9401 438159.5589 1609567 0.24%
    4960 998 439049.7278 206 439201.9401 438159.5589 1625779 0.24%
    5043 1058 438945.0955 207 439201.9401 438159.7499 1693379 0.24%
    5088 1088 438968.8020 184 439201.9401 438159.7499 1696736 0.24%
    5126 1101 438482.0065 231 439201.9401 438159.7499 1719856 0.24%
    5184 1130 438943.4659 240 439201.9401 438181.3193 1753048 0.23%
    5418 1297 438940.1925 239 439201.9401 438181.3193 1804530 0.23%
    * 5479+ 1334 438958.7173 438182.1193 1816055 0.18%
    * 5479+ 1334 438877.1814 438182.1193 1816055 0.16%
    * 5479+ 1334 438860.9146 438182.1193 1816055 0.15%
    * 5479+ 1334 438849.3216 438182.1193 1816055 0.15%
    * 5479+ 1334 438849.2019 438182.1193 1816055 0.15%
    5479 1332 439196.1488 93 438849.2019 438182.1193 1816055 0.15%
    Elapsed time = 1208.53 sec. (709626.64 ticks, tree = 72.39 MB, solutions = 20)
    5631 705 438836.5519 247 438849.2019 438182.1193 1872333 0.15%
    5775 769 438732.0640 248 438849.2019 438182.1193 1949075 0.15%
    5860 796 438847.3433 216 438849.2019 438362.7596 2012842 0.11%
    5904 807 438522.8320 250 438849.2019 438362.7596 2036172 0.11%
    6024 852 438610.8807 244 438849.2019 438362.7596 2102069 0.11%
    6044 856 438519.9762 220 438849.2019 438442.6668 2117816 0.09%
    6082 871 438521.8577 220 438849.2019 438442.6668 2157155 0.09%
    6298 982 cutoff 438849.2019 438454.1238 2279435 0.09%
    6336 993 438648.9910 222 438849.2019 438454.1238 2291946 0.09%
    6403 1030 438795.6841 226 438849.2019 438454.1238 2306185 0.09%
    Elapsed time = 1332.11 sec. (760502.27 ticks, tree = 34.57 MB, solutions = 23)
    6525 1112 438686.5683 217 438849.2019 438454.1238 2359435 0.09%
    6706 1160 438552.4929 227 438849.2019 438477.5091 2430512 0.08%
    6841 1232 438721.5008 223 438849.2019 438477.5091 2484216 0.08%
    7021 1296 438794.2567 214 438849.2019 438477.5091 2552279 0.08%
    7255 1376 438614.7104 239 438849.2019 438488.4449 2592408 0.08%
    7384 1419 438664.3905 288 438849.2019 438488.4449 2630558 0.08%
    7416 1433 438820.2687 223 438849.2019 438488.4449 2659449 0.08%
    7480 1458 438583.3285 250 438849.2019 438488.4449 2700153 0.08%
    7707 1525 438794.2667 314 438849.2019 438502.9697 2768685 0.08%
    7729 1523 438599.9996 227 438849.2019 438502.9697 2778443 0.08%
    Elapsed time = 1455.78 sec. (815128.49 ticks, tree = 61.76 MB, solutions = 23)
    7843 1557 438609.8219 131 438849.2019 438502.9697 2821142 0.08%
    * 7976+ 1622 438835.4986 438502.9697 2835198 0.08%
    * 8055+ 1653 438828.7114 438502.9697 2855733 0.07%
    * 8114+ 1681 438828.5016 438502.9697 2867672 0.07%
    8211 1562 438710.8101 223 438828.5016 438517.5144 2900723 0.07%
    8216 1564 cutoff 438828.5016 438517.5144 2900978 0.07%
    8363 1600 438761.2218 224 438828.5016 438517.5144 2940584 0.07%
    8746 1635 438622.3290 190 438828.5016 438555.4287 3078066 0.06%
    8866 1644 438612.9203 247 438828.5016 438555.4287 3094929 0.06%
    8994 1656 438731.9507 249 438828.5016 438555.4287 3152020 0.06%
    9098 1664 438815.7797 226 438828.5016 438555.4287 3189048 0.06%
    9466 1724 438664.6483 215 438828.5016 438555.4287 3306929 0.06%
    9515 1732 438640.9235 249 438828.5016 438589.5693 3311163 0.05%
    Elapsed time = 1597.44 sec. (876090.10 ticks, tree = 57.45 MB, solutions = 26)
    9529 1728 438697.8351 213 438828.5016 438589.5693 3321926 0.05%
    9641 1715 438805.9756 147 438828.5016 438589.5693 3360285 0.05%
    9707 1714 438670.6121 127 438828.5016 438589.5693 3374851 0.05%
    9850 1698 438750.8886 253 438828.5016 438589.5693 3408574 0.05%
    * 10111+ 1778 438814.2459 438589.5693 3498924 0.05%
    * 10127+ 1780 438814.0361 438589.5693 3499576 0.05%
    10169 1563 438697.2434 194 438814.0361 438619.6696 3503356 0.04%
    10241 1572 438672.9550 205 438814.0361 438619.6696 3556756 0.04%
    10283 1564 438809.5885 215 438814.0361 438619.6696 3570744 0.04%
    10403 1566 438802.8250 188 438814.0361 438619.6696 3631370 0.04%
    10637 1582 438659.2812 251 438814.0361 438619.6696 3671199 0.04%
    10837 1550 438771.8369 235 438814.0361 438619.6696 3689332 0.04%
    Elapsed time = 1717.94 sec. (924739.88 ticks, tree = 41.39 MB, solutions = 26)
    * 11282+ 1516 438799.5181 438659.0890 3724930 0.03%
    11282 1518 438727.3853 128 438799.5181 438659.0890 3724930 0.03%
    11347 1493 438760.7754 142 438799.5181 438659.0890 3730083 0.03%
    11571 1471 438773.3021 225 438799.5181 438659.0890 3767495 0.03%
    * 11630+ 1461 438799.5181 438659.0890 3769849 0.03%
    11706 1466 438723.5253 208 438799.5181 438659.0890 3774333 0.03%
    * 11839+ 1482 438799.5181 438659.0890 3787767 0.03%
    * 12122+ 1556 438795.7085 438659.0890 3814397 0.03%
    * 12152+ 1568 438795.4986 438659.0890 3815186 0.03%
    12241 1282 438721.1380 236 438795.4986 438708.6550 3827043 0.02%
    12635 1458 438735.7647 188 438795.4986 438708.6550 3854377 0.02%
    * 12854 1545 integral 0 438778.2835 438708.6550 3864368 0.02%
    12963 1607 438746.6209 160 438778.2835 438708.6550 3870167 0.02%
    13097 1659 438728.8261 200 438778.2835 438708.6550 3887142 0.02%
    * 13215 1591 integral 0 438766.5008 438708.6550 3889748 0.01%
    Elapsed time = 1830.91 sec. (973513.30 ticks, tree = 30.12 MB, solutions = 35)
    13529 1610 438754.6933 151 438766.5008 438708.6550 3899767 0.01%
    13954 1832 cutoff 438766.5008 438708.6550 3921231 0.01%
    14110 1889 438743.2243 194 438766.5008 438708.6550 3936242 0.01%

    Clique cuts applied: 1
    Cover cuts applied: 2
    Implied bound cuts applied: 145
    Flow cuts applied: 413
    Mixed integer rounding cuts applied: 1716
    Zero-half cuts applied: 2
    Gomory fractional cuts applied: 140

    Root node processing (before b&c):
    Real time = 157.34 sec. (83057.28 ticks)
    Parallel b&c, 8 threads:
    Real time = 1695.55 sec. (905119.09 ticks)
    Sync time (average) = 296.84 sec.
    Wait time (average) = 0.09 sec.
    ------------
    Total (root+branch&cut) = 1852.89 sec. (988176.37 ticks)

    Solution pool: 44 solutions saved.

    MIP - Integer optimal, tolerance (0.0001/1e-006): Objective = 4.3876650084e+005
    Current MIP best bound = 4.3872287624e+005 (gap = 43.6246, 0.01%)
    Solution time = 1852.92 sec. Iterations = 3962040 Nodes = 14912 (1152)
    Deterministic time = 988186.09 ticks (533.31 ticks/sec)

    ------------------------------
    ORE2021
    ------------------------------

    #DecisionOptimization


  • 2.  RE: MIP Performance improvement

    Posted Tue November 30, 2021 03:46 AM
    Hello, in general, here are some settings I try to play with for MIP performance:
    - increase the cuts for the 2 biggest groups (here flow and mir) and disable others.
    - change mip emphasis to 4 or 5.
    - try aggressive probing
    - increase the MIP heuristic effort
    - increase symmetry breaking
    - force LP method 2
    - use the polish after gap setting

    Switching to 12.10 or 20.1 which are the current active versions may also help.

    ------------------------------
    Vincent Beraudier
    ------------------------------