Integer Programming:Branch and Bound Branch and Bound.
Consider the following integer programming problem:
Max Z = -x1 +3x2
Subject to
-10x1 + 15x2 ≤ 20
5x1 + 8x2 ≤ 40
x1 ≤ 5
xi ≥ 0, xi's are integers
(i) Use Solver to find the initial linear relaxation (in step 0 for the branch and bound method) for this problem.
(ii) Show the graphical solution to this problem.
(iii) Define the first 2 sub-problems to be solved using the branch and bound method.
(iv) Illustrate what is going on using the graph from step (ii).