Integer LP by Branch and Bound: 23-Ind-A1 Operations Research, December 2014, Q5

Question 5: Integer LP by Branch and Bound (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Maximize $Z=x_1+2x_2$ s.t. $x_1+3x_2\le16$, $x_1+x_2\le7$, $x_1,x_2\ge0$ and integer.

Find. The integer-optimal $(x_1,x_2)$ and $Z^*$ by branch and bound.

Approach. Solve the LP relaxation graphically for an upper bound, branch on the fractional variable, resolve each sub-LP graphically, and stop once every open branch is either integer-feasible or bounded below the best integer solution found.

Root LP relaxation. The feasible region's vertices are $(0,0)$, $(7,0)$, $(0,16/3)$, and the intersection of the two binding constraints. Solving $x_1+3x_2=16$ and $x_1+x_2=7$ simultaneously: subtracting gives $2x_2=9\Rightarrow x_2=4.5$, $x_1=2.5$. Evaluating $Z=x_1+2x_2$ at all vertices, the maximum is at $(2.5,4.5)$: $$Z_{\text{LP}}=2.5+2(4.5)=\boxed{11.5\text{ (upper bound for any integer solution)}}.$$
Branch on $x_2$ (fractional at 4.5). Create two sub-problems: Branch 1 adds $x_2\le4$; Branch 2 adds $x_2\ge5$.
Branch 1 ($x_2\le4$). The new binding vertex is the intersection of $x_1+x_2=7$ and $x_2=4$: $x_1=3$. Checking the other constraint, $x_1+3x_2=3+12=15\le16$ — feasible, and this vertex is already integer: $$(x_1,x_2)=(3,4),\quad Z=3+2(4)=\boxed{11}.$$ No further branching needed on this side — record it as an incumbent.
Branch 2 ($x_2\ge5$). With $x_2\ge5$, constraint $x_1+3x_2\le16$ forces $x_1\le1$ when $x_2=5$ (and $x_2\le16/3=5.33$, so $x_2=5$ is the only integer value in range once $x_1\ge0$). Maximizing $x_1$ at $x_2=5$ gives $x_1=1$ (also satisfies $x_1+x_2=6\le7$): $$(x_1,x_2)=(1,5),\quad Z=1+2(5)=\boxed{11}.$$
Prune and conclude. Both branches terminate in integer-feasible solutions tied at $Z=11$, and $11$ is the best possible since the root LP bound was $11.5$ (no integer point can reach above $\lfloor11.5\rfloor=11$). Branch and bound therefore terminates with two alternate optima: $$\boxed{Z^*=11\ \text{at } (x_1,x_2)=(3,4)\ \text{or}\ (1,5).}$$

Final results — Question 5
Quantity	Value
LP relaxation optimum	$(2.5,4.5)$, $Z=11.5$
Integer optimum	$Z^*=11$
Optimal integer solutions	$(3,4)$ and $(1,5)$ (tied, alternate optima)

Topic: Branch and bound for integer linear programming.

Key relations: LP relaxation gives a valid bound ($Z_{\text{LP}}\ge Z_{\text{IP}}$ for a maximization); branching on a fractional variable partitions the feasible region without losing any integer point; a branch is pruned once its LP bound cannot beat the best integer incumbent.

Why this works: Rounding the LP optimum $(2.5,4.5)$ naively would give an infeasible or suboptimal point; branch and bound instead splits the search exactly at the fractional coordinate ($x_2\le4$ vs. $x_2\ge5$), so every integer point in the original region still lies in exactly one branch, and solving each branch's (smaller) LP relaxation is enough to certify optimality once the bounds close.

Common pitfall: Stopping after finding the first integer-feasible branch without checking whether a competing branch's bound could still beat it — here both branches happened to tie at 11, which must be verified rather than assumed.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 12 — branch-and-bound algorithms for integer programming.

Question 5 of 10: Integer LP by Branch and Bound

Question 5: Integer LP by Branch and Bound (15 marks)