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

Let item $j$ have weight $a_j$ and profit $p_j$. Define $D(j,b)$ as the largest profit obtainable from the first $j$ items with capacity at most the nonnegative integer $b$. Set $D(0,b)=0$. The last item is either absent or present once, giving the dynamic programming recursionThe two alternatives exhaust the feasible binary decisions. In the second alternative, deleting item $j$ leaves exactly the smaller subproblem with capacity $b-a_j$, which proves the recurrence.

Fill rows $j=1,\dots ,4$, and within each row capacities $b=0,\dots ,7$. Store which alternative attains each maximum. Backtrack from $(4,7)$: when exclusion was chosen, set $x_j=0$ and move to $(j-1,b)$; when inclusion was chosen, set $x_j=1$ and move to $(j-1,b-a_j)$. Ties may be resolved either way. Thus the stored values yield an actual optimal selection, not just its objective value.

For $n$ items and capacity $B$, the algorithm uses $O(nB)$ arithmetic operations and $O(nB)$ space with the full backtracking table. It is a pseudo-polynomial algorithm, since $B$ is a numerical capacity rather than its bit length. A value-only version can use one row, but must update capacities in decreasing order to avoid reusing the same item.

Applying the recurrence in source item order gives the complete tableAt $(4,7)$ inclusion wins, since $25+D(3,2)=40>D(3,7)=39$. Thus $x_4=1$ and the residual capacity is two. Items three and two are too heavy for it, and item one exactly fits. ConsequentlyIts weight is $2+5=7$. The recurrence proves that no binary selection with capacity seven has greater profit.

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.