Not that large MILP model took ages to obtain the optimal results

Answered

Comments

8 comments

  • Sonja Mars

    When is the first feasible solution found? Can you post the 5 log lines before and the 5 lines after this event?

    Thanks,

      Sonja

    0
    Comment actions Permalink
  • Ibrahim Fikry

    Dear. Dr.Sonja,

     

     I am facing the same issue in another MIP model, Could you please advise?

     

    Thanks in advance 

    0
    Comment actions Permalink
  • Sonja Mars

    Hi Ibrahim,

    Can you share a log file or parts of a log file that show the important stages of the solving?

    Thanks,

      Sonja

    0
    Comment actions Permalink
  • Ibrahim Fikry

    Dear Dr. Sonja,

     

     Here is the log file:

    Optimize a model with 583933 rows, 3007851 columns and 9740838 nonzeros
    Model fingerprint: 0x4267a30c
    Variable types: 130287 continuous, 2813372 integer (2812000 binary)
    Semi-Variable types: 192 continuous, 64000 integer
    Coefficient statistics:
    Matrix range [1e-01, 6e+05]
    Objective range [1e+00, 1e+00]
    Bounds range [1e+00, 3e+00]
    RHS range [1e+00, 1e+07]
    Presolve removed 282177 rows and 2702146 columns (presolve time = 7s) ...
    Presolve removed 350856 rows and 2702166 columns (presolve time = 10s) ...
    Presolve removed 351872 rows and 2702182 columns (presolve time = 16s) ...
    Presolve removed 351872 rows and 2767169 columns (presolve time = 20s) ...
    Presolve removed 415915 rows and 2767189 columns (presolve time = 25s) ...
    Presolve removed 415915 rows and 2767189 columns (presolve time = 31s) ...
    Presolve removed 415847 rows and 2767121 columns
    Presolve time: 30.98s
    Presolved: 168086 rows, 240730 columns, 995578 nonzeros
    Variable types: 128661 continuous, 112069 integer (112000 binary)

    Deterministic concurrent LP optimizer: primal and dual simplex
    Showing first log only...

    Presolved: 168086 rows, 240730 columns, 995578 nonzeros


    Root simplex log...

    Iteration Objective Primal Inf. Dual Inf. Time
    0 -6.8870400e+03 1.061600e+04 2.868687e+09 39s
    27564 -6.1515244e+03 2.779822e+03 1.934845e+10 40s
    54135 9.7138508e+10 0.000000e+00 3.319229e+09 44s
    67973 9.4368476e+10 0.000000e+00 4.419820e+10 45s
    95720 8.7804727e+10 0.000000e+00 1.130559e+10 50s
    146842 8.7675430e+10 0.000000e+00 1.879597e+10 55s
    189586 7.0040968e+07 0.000000e+00 1.319235e+09 60s
    207114 3.2795941e+07 0.000000e+00 2.675595e+09 65s
    223917 5.4836499e+06 0.000000e+00 9.813118e+08 70s
    238340 4.6060952e+05 0.000000e+00 4.798973e+07 75s
    264177 4.3146288e+05 0.000000e+00 1.150660e+06 80s
    285244 4.1915193e+05 0.000000e+00 2.414251e+06 85s
    308024 4.0950657e+05 0.000000e+00 4.344521e+06 90s
    327165 4.0382635e+05 0.000000e+00 1.053032e+06 95s
    349021 3.9731106e+05 0.000000e+00 1.183320e+06 100s
    371053 3.9257048e+05 0.000000e+00 3.550259e+05 105s
    390693 3.9089642e+05 0.000000e+00 1.909635e+05 110s
    405117 3.8830537e+05 0.000000e+00 5.644955e+03 115s
    420334 3.8812836e+05 0.000000e+00 1.091260e+03 120s
    433956 3.8808418e+05 0.000000e+00 2.494808e+02 125s
    441741 3.8806238e+05 0.000000e+00 1.279263e+05 130s
    443656 3.8803758e+05 0.000000e+00 4.024126e+03 136s
    445176 3.8802382e+05 0.000000e+00 1.005324e+04 141s
    446726 3.8801138e+05 0.000000e+00 1.683153e+04 145s
    448321 3.8799809e+05 0.000000e+00 3.882315e+03 150s
    449736 3.8798221e+05 0.000000e+00 1.835246e+04 155s
    451046 3.8797212e+05 0.000000e+00 6.098656e+03 160s
    Concurrent spin time: 0.00s

    Solved with dual simplex

    Root relaxation: objective 3.878547e+05, 72200 iterations, 123.81 seconds
    Total elapsed time = 201.84s
    Total elapsed time = 216.76s
    Total elapsed time = 231.60s
    Total elapsed time = 250.87s

    Nodes | Current Node | Objective Bounds | Work
    Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

    0 0 387854.684 0 8693 - 387854.684 - - 262s
    H 0 0 2.363126e+09 387854.684 100% - 266s
    0 0 387935.181 0 3917 2.3631e+09 387935.181 100% - 1042s
    H 0 0 4557969.6699 387935.181 91.5% - 1049s
    0 0 387975.383 0 4741 4557969.67 387975.383 91.5% - 1059s
    0 0 387975.383 0 4883 4557969.67 387975.383 91.5% - 1062s
    0 0 387983.223 0 4943 4557969.67 387983.223 91.5% - 1097s
    H 0 0 2555460.9099 387983.223 84.8% - 1105s
    0 0 387991.066 0 4950 2555460.91 387991.066 84.8% - 1109s
    0 0 387991.066 0 4931 2555460.91 387991.066 84.8% - 1111s
    0 0 388002.538 0 4925 2555460.91 388002.538 84.8% - 1148s
    H 0 0 444010.62999 388002.538 12.6% - 1157s
    0 0 388003.250 0 4918 444010.630 388003.250 12.6% - 1165s
    0 0 388003.250 0 4939 444010.630 388003.250 12.6% - 1168s
    0 0 388154.742 0 954 444010.630 388154.742 12.6% - 1206s
    0 0 388157.971 0 936 444010.630 388157.971 12.6% - 1213s
    0 0 388157.971 0 989 444010.630 388157.971 12.6% - 1214s
    0 0 388159.357 0 1023 444010.630 388159.357 12.6% - 1235s
    0 0 388160.706 0 999 444010.630 388160.706 12.6% - 1243s
    0 0 388160.706 0 1227 444010.630 388160.706 12.6% - 1244s
    0 0 388164.145 0 1051 444010.630 388164.145 12.6% - 1282s
    0 0 388164.208 0 1045 444010.630 388164.208 12.6% - 1287s
    0 0 388164.208 0 981 444010.630 388164.208 12.6% - 1288s
    0 0 388165.785 0 819 444010.630 388165.785 12.6% - 1325s
    0 0 388165.812 0 901 444010.630 388165.812 12.6% - 1332s
    0 0 388165.896 0 1211 444010.630 388165.896 12.6% - 1349s
    0 0 388165.899 0 1532 444010.630 388165.899 12.6% - 1355s
    0 0 388165.899 0 1495 444010.630 388165.899 12.6% - 1372s
    0 0 388165.899 0 966 444010.630 388165.899 12.6% - 1378s
    0 0 388165.899 0 1277 444010.630 388165.899 12.6% - 1394s
    0 0 388165.899 0 545 444010.630 388165.899 12.6% - 1523s
    H 0 0 393359.81406 388165.899 1.32% - 1595s

    Cutting planes:
    Gomory: 28
    Clique: 88
    MIR: 95
    Flow cover: 3
    Zero half: 134
    RLT: 104

    Explored 1 nodes (306422 simplex iterations) in 1618.32 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 5: 393360 444011 2.55546e+06 ... 2.36313e+09

    Solve interrupted
    Best objective 3.933598140566e+05, best bound 3.881658989644e+05, gap 1.3204%
    0
    Comment actions Permalink
  • Sonja Mars

    Hi,

    I am sorry, I don't see the issue in the log. It looks very different from the log of the original post.

    However, this is quite a big model with 3 million variables 0.5 million constraints, and almost 10 million nonzeros. Even after presolve there are almost 1 million nonzeros left over. Gurobi is able to reduce the MIP gap to less than 1.5% in less than 30 minutes. This does not sound too bad to me.

    • What are your time limit and your target MIP gap?
    • Have you tried to do some parameter tuning on this model?

    Best,

      Sonja

     

    0
    Comment actions Permalink
  • Ibrahim Fikry

    Dear Dr. Sonja,

     

     Thanks for your reply, I am sorry for using an old post to ask about a similar issue. 

     

    for your questions:

    • What are your time limit and your target MIP gap? I use certain termination criteria with soft limit and hard time with 2% gap and 5% gap.

     

    • Have you tried to do some parameter tuning on this model? Yes, I have tried tuning the model, and that's why I am asking as MIP focus, improve start node, etc. did not reflect any changes on the model which is strange for me as I used to improve my models using tuning parameters.

    Any advice regarding improving and decreasing  the solution time?

    0
    Comment actions Permalink
  • Sonja Mars

    Hi,

    I would try each of the following parameters on its own first

    MIPFocus=1

    Presolve=2

    Method=2

    Cuts=1

    CutPasses=3

    to see if there is any improvement in the runtime. I would then probably combine a few of those parameters. You can also try to run the parameter tuning tool for a while. Maybe it comes up with a good idea.

    Best regards,

      Sonja

    1
    Comment actions Permalink
  • Ibrahim Fikry

    Thanks Dr.Sonja

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk