MIP solver stopping criteria

For larger MIP models we often don't wait for a proven optimal solution. This just takes too long, and actually we are spending a lot of time in proving optimality without much return in terms of better solutions. There are a number of stopping criteria that are typically available:

1. Time Limit : stop after \(x\) seconds (or hours)
2. 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).
3. Absolute Gap: similar to relative gap, but can be used when the relative gap cannot be computed (division by zero or small number).
4. Node Limit: stop on number of explored branch & bound nodes.
5. 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.

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.