Past exam of the integer programming course of the University of Oxford / 2011 / 2 / c / Solution

For each branch and bound node, relax the unfixed binary variables to $[0,1]$. The fractional knapsack problem is solved by decreasing profit-to-weight ratios, hereIts value is an upper bound for the node's integer optimum. At the root, greedy filling gives $x=(1,1,1/2,0)$ and upper bound $\boxed{43.5}$, so branch on $x_3$.

In the child $x_3=0$, the relaxed optimum is $(1,1,0,2/5)$ with value $43$. Branch on $x_4$. Taking $x_4=1$ leaves capacity two, giving the integral solution $(1,0,0,1)$ of value $40$, our incumbent. Taking $x_4=0$ gives the integral relaxed optimum $(1,1,0,0)$ of value $33$, so that node is closed.

In the child $x_3=1$, item four cannot be selected in any integer feasible solution, since their combined weight is nine. Fixing $x_4=0$ is therefore valid binary feasibility propagation. Its LP optimum is $(1,1/3,1,0)$ with value $42$. Branch on $x_2$. The child $x_2=1$ leaves no residual capacity and has integral solution $(0,1,1,0)$ of value $39$. The child $x_2=0$ has integral solution $(1,0,1,0)$ of value $36$. Both are below the incumbent.

The complete short search isAll integer feasible solutions lie in these branches, and every terminal node is integral with value at most forty. Therefore the LP bounds and incumbent certify $\boxed{z_{\mathrm{IP}}=40}$ independently of the dynamic program.