Skip to main content

Branch-and-bound gap does not close

Answered
Meijun Chen
Gurobi-versary
First Comment
First Question

Dear Gurobi Support Team,

I have an MILP optimization problem that I observe takes very long to close the gap between incumbent and best bound. Is there any way to perhaps change the setting of root node so that the gap is closed more easily? Here is the log file:

Thank you very much in advance!

Best regards,

Meijun

Related to

0

Comments

3 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Meijun,

    Your model is extremely large. Thus, it may indeed take days to reach an acceptable MIPGap. Anyway, you could try setting the NoRelHeurTime parameter to activate the so-called No Relaxation heuristic which will search for feasible points even before the root node is solved. Given the size of your model I would set NoRelHeurTime=3600/7200/10800. 

    Moreover, you should try turning off PreSparsify and Cuts, i.e., set PreSparsify=-1 and Cuts=0. You could also set MIPFocus=1.

    You should also try upgrading to v10.

    Best regards, 
    Jaromił

    0
  • Meijun Chen
    Gurobi-versary
    First Comment
    First Question

    Dear Jaromil,

    Thanks for your advice, it helps a lot! I have two questions, and I would appreciate it if you could give some insights.

    1. In a model that I attempt to use Gurobi to solve, I observe that using NoRelHeurTime of 10800 does not necessarily help close the MIP Gap compared to 7200. Is the outcome of the heuristic algorithm relatively random? And does longer heuristic time lead to quicker gap closing at the root node? I am not sure whether further increasing NoRelHeurTime would help. Below are parts of the log file of two runs with only the difference in NoRelHeurTime:

    NoRelHeurTime = 7200

    NoRelHeurTime = 10800

    2. I observe that the model does not close the MIP gap after a long solving time and that IntInf decreases very slowly. Does that mean the model has walked in some dead-end cycle?

    ...

    Thank you very much in advance!

    Best regards,

    Meijun

    P.S. Thanks for the advice to upgrade to v10, I have been using v9.5.2 since the cluster only have the license for this version...

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Meijun,

     In a model that I attempt to use Gurobi to solve, I observe that using NoRelHeurTime of 10800 does not necessarily help close the MIP Gap compared to 7200. Is the outcome of the heuristic algorithm relatively random? And does longer heuristic time lead to quicker gap closing at the root node? I am not sure whether further increasing NoRelHeurTime would help.

    The No Relaxation heuristic is as its name already states only a heuristic. Thus, no guarantee can be made about any improvement for a given time frame. From the log you posted, it looks like once Gurobi has a decent feasible solution at hand, it is able to improve quite quickly. In this case, I would rather tend to decrease the time spent in the No Relaxation heuristic. Let's say, the No Relaxation heuristic finds a first feasible solution after 1800s, I would then set NoRelHeurTime=3600 or even a bit less.

    Overall, given the size of your model and the vast amount of discrete variables, it is possible that bringing the MIPGap significantly below 1.5% will be very hard.

    From here I see the following options.

    • You could rethink whether a MIPGap of 1.5% is acceptable for your application. If you don't know it a priori, you could write a MIPNODE callback where you get the current best bound and incumbent and compute the MIPGap. Please note that you have to compute the MIPgap yourself as there is no callback querry to get it, the MIPGap formula can be found here. Once you have computed the MIPGap in the callback, you could check the current runtime and decide whether it is worth to continue the optimization and if not then terminate the run.
    • You could try experimenting with other parameters discussed in the Most important parameters section.

    Thanks for the advice to upgrade to v10, I have been using v9.5.2 since the cluster only have the license for this version...

    Since you are at an academic institution, you could ask your system administrator to reach out to us via a Gurobi Support Request and ask for an updated license. The process is simple and quick, such that you would be able to use the latest Gurobi version quite soon.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post