Skip to main content

Large MIP Model Stops Progressing - Many Equivalent Solutions?

Answered

Comments

3 comments

  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi Ralph,

    You might want to experiment with the following:

    • The model is big. It has 2.5 million binary variables. It might be a good idea to ensure the presolved model is as small and as tight as possible. You can experiment with more aggressive settings for the parameters Presolve (2), Symmetry (2), and PreSparsify (1).
    • The log shows that the Gurobi Optimizer is struggling in finding a good incumbent quickly. You can consider experimenting with the parameter NoRelHeurTime which enforces the Gurobi Optimizer to run the NoRel (no relaxation) heuristic before the root relaxation. 
    • Bumping up the default value of the Heuristics parameter and turning off the Cuts (Cuts=0) are other ideas that you can experiment with. Setting Cuts=0 makes sense because the log shows that the bound does not move from the value obtained from the root relaxation.

    Best regards,

    Maliheh

    0
  • RALPH ASHER
    First Comment
    First Question

    Thank you Maliheh.  I'm running it now with Presolve=2, PreSparsify=1, Symmetry = 2,
    NoRelHeurTime=700,Cuts=0,Heuristics=0.3 in the parameters.  Aggressive Presolve took much longer, but it's exploring many more nodes in the same approximate time as before.

     

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

         0     0  129.97400    0  753   -0.00000  129.97400      -     - 7988s
    H    0     0                       7.2810187  129.97400  1685%     - 7998s
    H    0     0                      16.4615871  129.97400   690%     - 8052s
         0     0  129.97400    0  567   16.46159  129.97400   690%     - 9777s
    H    0     0                      17.7285534  129.97400   633%     - 20042s
    H    0     0                      24.7837486  129.97400   424%     - 20243s
         0     2  129.97400    0  474   24.78375  129.97400   424%     - 20940s
         1     4  129.97400    1 1009   24.78375  129.97400   424% 60713 21161s
         3     8  129.97400    2  790   24.78375  129.97400   424% 45273 21217s
         7    16  129.97400    3  813   24.78375  129.97400   424% 21157 21419s
        15    24  129.97400    4  811   24.78375  129.97400   424% 17315 21503s
        23    32  129.97400    5  723   24.78375  129.97400   424% 12226 21534s
    H   31    40                      33.1828600  129.97400   292%  9387 22750s
    H   35    40                      39.8238175  129.97400   226%  8682 22750s
        39    48  129.97400    7  772   39.82382  129.97400   226%  8147 22774s
        47    60  129.97400    8  970   39.82382  129.97400   226%  7092 22880s
        59    88  129.97400    9  961   39.82382  129.97400   226%  6248 24440s
    H   64    88                      41.2301039  129.97400   215%  5847 24440s
    H   87   113                      41.7123821  129.97400   212% 11735 27186s
    H   98   113                      45.9968559  129.97400   183% 11101 27186s
    H  112   185                      47.0023530  129.97400   177% 12421 30039s
    H  120   185                      48.1180504  129.97400   170% 13344 30039s
       175   185  129.97400   12 3056   48.11805  129.97400   170% 12562 30040s
       184   272  129.97400   30 1094   48.11805  129.97400   170% 12877 32011s
    H  271   347                      49.3286311  129.97400   163% 11005 33184s
       346   411  129.97400   40  529   49.32863  129.97400   163%  9780 34932s
    H  410   471                      50.1459907  129.97400   159%  8770 38480s
    H  424   471                      52.5408294  129.97400   147%  8801 38480s
       470   559  129.97400   42  525   52.54083  129.97400   147%  8235 39051s
    H  558   647                      52.8061270  129.97400   146%  7268 39874s
    H  580   647                      52.8507362  129.97400   146%  7007 39874s

    0
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi Ralph, 

    I think you mean you used NoRelHeurTime=7000. It apparently did not help at all and could not find an incumbent better than the one found by a heuristic immediately after presolve. You might want to discard this parameter. 

    • The log again shows that the Gurobi is struggling to find a high quality incumbent. How hard is it  to construct a feasible solution for this problem using a local search type heuristic? If it is relatively easy, you might want to consider providing that as an initial solution to give Gurobi a good start for proving optimality.
    • You might also consider experimenting with parameters such as ImproveStartTime, ImproveStartGap, or ImproveStartNode to completely change the strategy of Gurobi and give up on proving optimality and see what the best feasible solution you might be able to get.

    Best regards,

    Maliheh

     

    0

Please sign in to leave a comment.