= 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, here
$$
\frac{15}2>\frac{18}3>\frac{21}4>\frac{25}5.
$$
Its 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 is
$$
\begin{array}{l|c|c}
\text{Node restrictions}&\text{LP upper bound}&\text{Outcome}\\\hline
\text{none}&43.5&\text{branch on }x_3\\
x_3=0&43&\text{branch on }x_4\\
x_3=0,\ x_4=1&40&\text{integral incumbent}\\
x_3=0,\ x_4=0&33&\text{close}\\
x_3=1,\ x_4=0&42&\text{branch on }x_2\\
x_3=1,\ x_4=0,\ x_2=1&39&\text{close}\\
x_3=1,\ x_4=0,\ x_2=0&36&\text{close}
\end{array}
$$
All <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.
Back to article page
