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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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 known solution increased by a small amount ($10^{-10}$). 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 $10^{-10}$ is just to avoid dividing by zero should the best node LP value be 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$
4
  • $\begingroup$ The CPLEX documentation reports the relative gap calculation dividing over the best integer solution value. Is this the one reported in the branch and bound log, or is it the one you mention above? @prubin $\endgroup$
    – user3487128
    Commented Dec 27, 2020 at 23:56
  • $\begingroup$ Oops, you're correct, I had the wrong term in the denominator (and also used the wrong offset -- it's 1e-6, not 1). I've fixed that above. Thanks for the catch. $\endgroup$
    – prubin ♦
    Commented Dec 28, 2020 at 20:16
  • $\begingroup$ (I apologize for adding this comment as an answer, but I wasn't allowed to add as comment) The mipgap defined for CPLEX at the AMPL website ampl.com/products/solvers/solvers-we-sell/cplex/options doesn't match the one at the IBM website ibm.com/support/knowledgecenter/SSSA5P_12.9.0/… and so the reason for my original comment. Looking at AMPL/CPLEX logs from the past, I see the gap column in the B&B log calculated by dividing the absolute gap by the best integer (incumbent). What am I missing? Thanks! @prubin $\endgroup$
    – user3487128
    Commented Dec 28, 2020 at 22:55
  • $\begingroup$ I checked, and dividing by best integer has been the way CPLEX has done it since at least version 7.5. My original (erroneous) answer matched what's on the AMPL site, but I did not get it from there. I wonder if maybe some prehistoric version of CPLEX used that formula, so it made its way into the AMPL documentation, then CPLEX changed but the AMPL docs did not catch up? (Just speculating.) $\endgroup$
    – prubin ♦
    Commented Dec 29, 2020 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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