Terminate optimisation if objective value is close to predefined MIP gap but above a certain threshold

[anne...@gmail.com]

Hey guys,

I am calling the same MILP model with different input parameters a few thousand times in a row. So let's say the 500ths run of my MILP has returned an objective value of 1000 and my MIP gap is set to 1%. I now want gurobi (with I am using with spyder for python) to terminate every following optimisation, as soon as it is clear that the solution will not drop below 1000 at an gap of 1%. Actually I am unsure if there is such an criterion that is reliable. I basically do not want to waste time on running optimisations that for sure will not return a better solution than the best I have already found. Currently a few solutions take a very long time to optimise further from let's say 1.5% to 1%. I have already set a time limit so that this effect should be limited now.  After termination I need gurobi to return the current objective value just as it would if the optimisation was completed, so that it can be handed over the next set of input paramters automatically.

Does anybody have an idea how to solve this?

Thanks a lot in advance!
Anne

[Ed Rothberg]

You can implement custom termination criteria using a callback.  Look at our callback.py example for an example of how to do this.

Ed

[anne...@gmail.com]

Hey Ed,

thanks for the hint. But still I am not sure how to implement a condition that says "the model with the current set of paramerers can never reach an objective value better than the best that was ever found, so terminate". Would you mind helping me with this? Thanks a lot!

Anne

[Tobias Achterberg]

Hi Anne,

I don't quite understand the problem that you are facing. Let me rephrase in my
own words to make sure that there is no misunderstanding:

You are solving some MIP problem X, and Gurobi terminates with a solution of
value, say, 1000, that is within the required MIP gap of 1%. Thus, you know that
there is no solution that is better than 990 (assuming you are minimizing).

Now you want to solve a related problem Y. Does this problem have the same
objective function? I.e., does it make sense to restrict the objective function
value to 1000? If so, then you can just use the "Cutoff" parameter and set it to
1000 before solving Y. If the objective function is not the same, but you can
convert the 1000 for X into some corresponding objective value for Y, then again
you can use the "Cutoff" parameter.

If converting of objective values between successive models is not that easy or
if the abort criterion is not a simple cutoff threshold, then you can implement
a callback function that periodically checks the current primal and dual bound
and potentially the incumbent vector during the Y solve and aborts the
optimization as soon as you know that the problem became uninteresting.

Regards,

Tobias

[anne...@gmail.com]

Hi Tobias,

thanks for your very helpful reply! 

I actually did not know the cutoff parameter... It probably would do the trick, the only disadvantage is (according to the reference manual) that it does not return information on the best incumbent solution Gurobi has found already. I actually do need some kind of objective value given back by Gurobi in order to rank and process my solutions X,Y, ... for the following MIPs Z,ZZ,.... 

Would a callback function return information on the found solution, even if the optimisation was terminated? In that case I could implement a callback function that checks whether the current LP relaxation is better than my previously found solution (1000). If it is, optimisation was run normally. If it could never be better, it could set the MIPGap to e.g. 5%. In this case even the "bad" MIPs would return a (less precise) objective value I could use for setting up my following MIPs Z,ZZ etc., but it would be less time consuming. Is that roughly what a callback can do? 

Thanks a lot again, Tobias! Your help is much appreciated. 

Anne

[anne...@gmail.com]

I just went through the callback codes - is there a possibility to get the root relaxation?
And please feel free to correct me if the root relaxation wouldn't already be sufficient for the purpose I described above.
Thanks again!

[Tobias Achterberg]

I don't think that you need anything elaborate like comparing to the root
relaxation. You can just use the cutoff value. After Gurobi terminates, for
whatever reason, may it be a time limit or a MIP gap or hitting the cutoff, you
can always query the best solution found so far. Of course, if you hit a time
limit or the like, this solution is not necessarily optimal.

In your case, if you set a cutoff, what can happen is that Gurobi returns and
says the problem is infeasible. This would then mean that the solution that
generated the cutoff value that you installed is actually optimal for the problem.

Tobias

[anne...@gmail.com]

Okay, i'll give it a try. Thanks for answering! But is there anyway a way to retrieve the root's solution in a callback? Maybe it will be preferable in my case to go with the method of adjusting the mip gap depending on the problem. I would like to try out both ways!
Thank again :)

[Tobias Achterberg]

Sure. From your callback, if where == MIPNODE, query the MIPNODE_OBJBST,
MIPNODE_OBJBND, and MIPNODE_REL callback infos, depending on what you need.
Details can be found in the documentation at

http://www.gurobi.com/documentation/6.0/refman/c_grbsetcallbackfunc.html
http://www.gurobi.com/documentation/6.0/refman/c_grbcbget.html
http://www.gurobi.com/documentation/6.0/refman/callback_codes.html


Regards,

Tobias