3
$\begingroup$

I would like to set a stop condition combined of a timelimit and a relative MIP gap. So I would like AMPL/CPLEX to look for the solution of my LP for an hour and if there isn't a solution stop if or as soon as a relative MIP gap of X percent has been reached.

For clarification, could you try to explain to me the exact meaning of a MIP gap? I was looking for a second stop condition to get at least somewhat close to a solution and not randomly stopping after time X has passed. I understand the relative MIP gap as an educated guess on how much the currently found solution is distant from the best possible solution therefore

$$\frac{\text{current objective function result}}{\text{best possible objective function result}}$$

but the actual relative MIP gap seems to be a little bit more complicated

Relative tolerance for optimizing integer variables: stop if

$$\text{abs}((\text{best bound}) - (\text{best integer})) < \text{mipgap} \times (1 + \text{abs}(\text{best bound})).$$

$\text{Default} = 1\cdot 10^{-4}$ must be between $1\cdot 10^{-9}$ and $1$.

I am not sure how exactly best bound and best integer is defined, on the other hand I am not even close to an expert in optimisation stuff.

$\endgroup$
3
$\begingroup$

Your ratio current/best possible is not itself a gap; it is part of what you would use to compute the relative gap.

The relative gap defined by CPLEX is the absolute difference between the objective solution of the best known solution (the incumbent, "best integer" in the formula you quote) and the best known bound ("best bound" in the formula), divided by the absolute value of the best bound increased by 1. The best bound will usually be the smallest objective value (in a min problem; largest in a max problem) of the node LP among all live nodes. Adding 1 is just to avoid dividing by zero should the best node LP value be zero (or generating a huge gap if the best node LP is close to zero).

You can specify both a relative gap limit and a time limit, in which case CPLEX will stop the first time either criterion applies. In other words, if it gets the relative gap below your limit before the time limit is reached, it stops. If not, it stops at the time limit. Is this what you want?

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.