Stopping AMPL/Gurobi after the objective function reaches a specific value

[Ege]

Hello, 

I wanted to find out whether it is possible to stop AMPL/Gurobi after a specific objective function has been reached. 

So in other words, rather than setting a target optimality gap, you would set a specific objective function value and once the value of the incumbent or best current solution reaches that set value, AMPL/Gurobi would stop solving. 

Thank you, 

Ege

[Ege]

Any ideas or suggestions?

[victor.z...@gmail.com]

Hello Ege,

I don't see a Gurobi option that allows this. You can parse the solution log and interrupt gurobi with SIGINT when it reaches the desired objective value, but it will require some scripting outside of AMPL.

HTH,

Victor

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Robert Fourer]

Gurobi does not have a built-in option of the sort you describe. In fact it is lacking two options of this kind: one to stop when the upper bound reaches a certain value, and one to stop when the lower bound reaches a certain value. I haven't noticed options of these kinds in other MIP solvers, either. Perhaps the developers are thinking, How can you know what value to stop at, when you don't know the optimal solution (to within some tolerance)? However, considering the number of times your question has been asked, it seems that in a few applications one does know a value beyond which the optimization is no longer significant or interesting. I recall a case where the purpose of the optimization was to determine whether the maximum was negative, and so it was desired to stop as soon as the lower bound reached zero.

You may see advice that you can get Gurobi to work in the desired way by writing a callback function. However since callbacks are not currently supported by the AMPL interface, the only way to follow this advice is to rewrite your entire model and your data-handling using one of the Gurobi APIs, which is a lot of trouble to implement such a simple condition.

You may also see advice to add directives of the form 'cutoff=<objval> solnlimit=1' to your gurobi_options string, where <objval> is replaced by the number that is your target objective function value. However this does not do what you have in mind, which is to have Gurobi run in the usual way and to stop as soon as it finds an incumbent solution whose objective value is at least as good as your target. Instead it converts your optimization into a feasibility problem, which in general is a harder problem and in any case results in Gurobi making a quite different search.

Possibly a more promising approach is to introduce a new variable Z >= 0, and to minimize Z subject to

Z >= <objective expression> - <objval>

(or similarly for maximization). I don't know how Gurobi reacts to problems of this form, but it appears to allow the objective to start at a value greater than <objval> and to be progressively reduced, and it should stop with an optimal value of Z = 0 as soon as the objective has a value less than or equal to <objval>.

Bob Fourer
am...@googlegroups.com

=======

[Ege]

Thank you for your responses, they were quite informative. 

I found a workaround to my problem, and in a way I think it's because I got lucky with the formulation of my model. It just so happens that the "Best Bound" (or relaxed) solution of my models are always zero. And the goal of my models is to minimize the terms in the objective function down to a value of zero. So, the optimality gap is always 100%, until you finally reach an objective function value of zero, which ends up giving you a 0% optimality gap. This was the reason why I wanted to look for an ending criterion which would allow me to avoid having to set a minimum relative optimality gap of some sort, because the parameter "mipgap" became more or less pointless to use. This was especially important for models where the objective function value could not be reduced to zero even after days or weeks of solution time, but a solution with a small enough objective function value would still be an acceptable solution.

I realized that Gurobi parameter "MIPGapAbs" allows me to achieve this, through the selection of an absolute difference in optimality (|Best Integer-Best Bound|) as an ending criterion for my models. The fact that "Best Bound" is always zero throughout the solution of my models helps me select a more or less accurate target for the objective function value (Best Integer) to end the solution process. 

Ege

[aminhoss...@gmail.com]

This was my question for a long time and there doesn't seem to be such a parameter defined for Gurobi, nor for Cplex as far as my search goes.
However, there is a way around this! Gurobi has two parameters "solutionlimit" and "cutoff". The cutoff parameter=inc makes Gurobi disregards any integer solution found which is worse than the value "inc". The solutionlimit parameter=lim, terminates Gurobi when "lim" number of integer solutions are found. Thus, setting solutionlimit=1, cutoff=inc+epsilon , results in the solver stopping at the first integer solution that is better than "inc+epsilon", which should be the incumbent value! 

[Robert Fourer]

This same strategy was described today on the Gurobi user forum, but as Renan Garcia notes there, it can be disappointingly inefficient. Because it discards integer solutions that do not meet the target, it cannot take advantage of solution improvement heuristics that rely on having an incumbent feasible solution. As a result Gurobi sometimes gets to the target a lot slower than it does when proceeding in the usual way, by finding a series of progressively better incumbents.

As always, the performance of a MIP optimizer is highly problem-specific, so you shouldn't hesitate to try this idea to see whether it works well for your particular problem.

Bob Fourer
am...@googlegroups.com

=======