What are Bounds in Branch Bound

Question

I am looking at a video to understand branch and bound more. Specifically, the one found at this link: (21) Ch06-03 Branch and Bound Method (B&B) - YouTube.

I have two questions:

1. Around 9:44, I'm not sure why the upper bound for node 3 to 10.25, but kept at 11.02 for node 2. Shouldn't the expected upper bound be the same for all nodes at one level? Based on this article https://www.gurobi.com/resource/mip-basics/, the upper bound for node 3 should be 10.25. To quote the article: "There are two additional important values we need to introduce to complete our description of branch-and-bound. First observe that, once we have an incumbent, the objective value for this incumbent, assuming the original MIP is a minimization problem, is a valid upper bound on the optimal solution of the given MIP. That is, we know that we will never have to accept an integer solution of value higher than this value. Somewhat less obvious is that, at any time during the branch-and-bound search we also have a valid lower bound, sometimes call the best bound. This bound is obtained by taking the minimum of the optimal objective values of all of the current leaf nodes."

2. I am dealing with a minimization problem rather than a maximization one as shown in the video. So in this case, would my Upper Bound be the best integer solution found so far and would the lower bound will be best value for the relaxed problem or best value overall i.e. considers both the objective value for the relaxed solution and feasible solutions?

3. Any recommended books for optimization in particular branch and bound?

Answer 1

For a minimization problem:

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

For a maximization problem:

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