3
$\begingroup$

For a minimization problem, when running a branch & bound algorithm, I understand that:

  • Every integer feasible solution provides an upper bound on the optimal objective value of the original problem.
  • The lower bound for each branch-and-bound node arises from solving the linear programming relaxation at that node, and the minimum of lower bounds (across all active leaf nodes) is a lower bound on the optimal objective value of the original problem.

I am having some troubling understanding the following:

  1. How can the minimum of lower bounds not be at the root node?
  2. In the graphs of this link, we can see that the lower bound is increasing with time. Why (or how) does this bound change during thevprocess?
$\endgroup$
1
  • $\begingroup$ Don't forget any lower bound is a global lower bound. It's a guarantee that there is no solution with an objective value lower than this bound. It certainly wouldn't make sense for it to decrease over time. $\endgroup$
    – Riley
    Commented Apr 28 at 0:06

1 Answer 1

4
$\begingroup$

The global lower bound is initially at the root node. But after you branch for the first time, the root is no longer an active node. Branching excludes some fractional solutions and therefore reduces the feasible region, so the global lower bound either stays the same or increases.

$\endgroup$
0

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.