- Time Limit : stop after \(x\) seconds (or hours)
- Relative Gap: stop if gap between best possible bound and best found integer solution becomes less than \(x\%\). Different solvers use different definitions (especially regarding the denominator).
- Absolute Gap: similar to relative gap, but can be used when the relative gap cannot be computed (division by zero or small number).
- Node Limit: stop on number of explored branch & bound nodes.
- Iteration Limit: stop on number of Simplex iterations. This number can be huge.
I have ordered these stopping criteria in how useful they are (to me). Time limit is by far the most important: just tell the solver how long we are willing to wait. Stopping on an achieved gap is also useful. I don't remember ever using a node or iteration limit.
If you specify several limits, typically a solver will stop as soon as it hits any one of the specified limits. In other words: multiple stopping criteria are combined in an "or" fashion.
If you specify several limits, typically a solver will stop as soon as it hits any one of the specified limits. In other words: multiple stopping criteria are combined in an "or" fashion.
When stopping on a time limit, it is still important to inspect the final gap. A small gap gives us a guaranteed quality assurance about the solution.
For large models the tail is often very long, and we probably see hardly any movement: no new integer solutions are found and the best bound is moving very slowly (and moving less over time). So I really want to stop if there is not much hope for a better solution.
I would suggest another possible stopping criterion:
stop if the time since the last new (and improving) integer solution exceeds a time limit
If the time since that last new integer solution is large, we can infer that the probability of finding a better solution is small. We can also interpret this as resetting the clock after each new integer solution. I don't think any solver has this. Of course, for some solvers, we can implement this ourselves using some callback function.
Totally agree - I have done this using e.g. callbacks for a number of projects.
ReplyDeleteI would add another refinement that I have used and that is to keep track of the difference in the objective value between the current incumbent and what it was some fixed time ago. Then we can stop if the solver has not made at least 0.1% improvement in the objective value during the last 10 minutes for example. This is useful if there are very many similar solutions near to the supposed optimal value, and we might get a prolonged sequence of solutions that are improving but only by a tiny amount.
To paraphrase: as long as you are making *worthwhile* progress in finding better solutions, keep going.
Just added this stopping criterion to Cbc:
ReplyDeletehttps://github.com/coin-or/Cbc/commit/f24335428f75dacf6913dbdee5fac698828b7159
Cool !!
DeleteI've just added this for some of my very long running MIPs. Implemented it on the Gurobi callback using two parameters: max time without a material change to the integer solution & a percentage tolerance for improvement (i.e. a definition of 'material').
ReplyDeleteAt the moment it is just a hammer (combined with a global runtime timeout and various other stopping criteria) that we are still tuning, but it is clearly very useful and has kicked in to save our users from situations of long-runtime for no gain.
I see the next step is to apply this criteria with tighter parameters but only in multi objective MIPs where little value is to be gained in the final few tiers.