Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2018 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 170 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming, the simplex method & sensitivity analysis/duality (ch. 3–4/6), integer programming & branch and bound (ch. 12), queueing theory (ch. 17), decision analysis (ch. 15), computer simulation (ch. 20). Nahmias, Production and Operations Analysis — single-period (newsvendor) and multi-period (dynamic lot-sizing / Wagner–Whitin) inventory models.
Question 10: Integer LP — Branch and Bound (15 marks)
Given. Maximize $z=x_1+2x_2$ subject to $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 maximum $z$ via branch and bound.
Approach. Solve the LP relaxation graphically; if a variable comes out fractional, branch on it into two sub-problems (round-down and round-up bounds), re-solve each relaxation, and stop once every open branch is either integer-feasible or provably no better than the best integer solution found.
Feasible region (green). Hollow blue circle: LP-relaxation optimum $(2.5,4.5)$, $z=11.5$. Filled red circles: the two alternate integer optima $(3,4)$ and $(1,5)$, each $z=11$.
Solve the LP relaxation graphically. The feasible region is a quadrilateral with vertices $(0,0),(7,0),(2.5,4.5),(0,16/3)$; evaluating $z=x_1+2x_2$ at each gives the maximum at $(2.5,4.5)$:
$$\boxed{\text{Root LP: } x_1=2.5,\ x_2=4.5,\ z=11.5}$$
$x_2=4.5$ is fractional, so branch on $x_2$: $x_2\le4$ vs. $x_2\ge5$.
Branch A ($x_2\le4$). Adding $x_2\le4$ to the LP, the new optimal vertex is where $x_2=4$ meets $x_1+x_2=7$ (the tighter of the two original constraints at $x_2=4$, since $x_1+3(4)\le16\Rightarrow x_1\le4$ is looser than $x_1\le3$ from $x_1+x_2\le7$):
$$\boxed{\text{Branch A: } x_1=3,\ x_2=4,\ z=11}$$
Both variables are integers — this branch is fathomed (integer-feasible), giving an incumbent of $z=11$.
Branch B ($x_2\ge5$). Adding $x_2\ge5$, feasibility also needs $x_1+3x_2\le16\Rightarrow x_1\le16-3x_2$, which forces $x_2\le16/3=5.33$ for any $x_1\ge0$ to exist — so $x_2$ can only be the integer 5 in this branch. At $x_2=5$: $x_1\le\min(16-15,\,7-5)=1$:
$$\boxed{\text{Branch B: } x_1=1,\ x_2=5,\ z=11}$$
Also integer-feasible, again $z=11$.
Compare against the root bound and conclude. Since $x_1,x_2$ are integers, $z=x_1+2x_2$ is always an integer, so no integer solution can exceed $\lfloor11.5\rfloor=11$ — the root LP relaxation's own bound. Both branches already achieved $z=11$, so neither can be improved and both are pruned by bound; no further branching is needed.
$$\boxed{z^*=11,\quad \text{attained at }(x_1,x_2)=(3,4)\ \text{or}\ (1,5)\ \text{(two alternate optima)}}$$
