1
$\begingroup$

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and dual bound (as shown here) is not clear to me, nor what the optimality gap is, or when a MIP can be solved optimally.

$\endgroup$

1 Answer 1

4
$\begingroup$

For a minimization problem, the lower bound arises from the linear programming relaxation and is also called a dual bound, and the upper bound arises from a feasible solution and is also called a primal bound. That situation matches the linked picture.

For a maximization problem, the upper bound arises from the linear programming relaxation and is also called a dual bound, and the lower bound arises from a feasible solution and is also called a primal bound.

The definition of optimality gap varies by solver and can be confusing to interpret when the bounds have opposite sign, but the general metric is a nonnegative ratio: $$\frac{\text{upper bound} - \text{lower bound}}{\epsilon+\text{absolute value of either lower bound or upper bound}},$$ where $\epsilon$ is a small positive constant to avoid division by $0$. The idea is that the gap decreases to $0$ as the solver finds better bounds, so it is a measure of progress toward optimally solving the problem. Most solvers allow you to set an optimality tolerance as a termination criterion so the solver will stop when it finds a feasible solution that is provably within that optimality gap.

$\endgroup$

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.