Consider the 0-1 knapsack instance $$ \begin{align*} n &= 7, \ (p_j) &= (70, 20, 39, 37, 7, 5, 10), \ (w_j) &= (31, 10, 20, 19, 4, 3, 6), \ C &= 50, \end{align*} $$ whose binary program is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 70x_1+20x_2+39x_3+37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 31x_1+10x_2+20x_3+19x_4+4x_5+3x_6+6x_7 \le 50 \ & \boldsymbol{x} \in {0,1}^3. \end{alignat*} $$

The algorithm requires items sorted by non-increasing efficiency $p_j/w_j$. $$ \frac{p_j}{w_j} = \left(\frac{70}{31}, \frac{20}{10}, \frac{39}{20}, \frac{37}{19}, \frac{7}{4}, \frac{5}{3}, \frac{10}{6}\right) \approx (2.258, 2.000, 1.950, 1.947, 1.750, 1.667, 1.667) $$ This sequence is already non-increasing, so the items keep their given order.

Node 0 (root)

No items are decided yet, so $j=1$, $z=0$, $C=50$. The undecided items $1,\dots,7$ form a continuous knapsack problem over capacity $50$, solved with Dantzig's greedy algorithm.

Packing items $1$ and $2$ whole uses weight $w_1+w_2=41 \le 50$. Item $3$ no longer fits whole since $w_1+w_2+w_3=61>50$, so it is the critical item and gets packed fractionally with the remaining capacity $50-41=9$ out of $w_3=20$. $$ F(\boldsymbol{x}^*) = p_1+p_2+p_3\cdot\frac{9}{20} = 70+20+39\cdot\frac9{20} = 107.55 $$ The profits are integers, so the Dantzig bound rounds this value down. $$ U = \lfloor 107.55 \rfloor = 107 $$ This gives $z+U=0+107=107$, the initial upper bound $B_{up}=107$. No complete solution exists yet, so the incumbent starts at $B_{low}=-\infty$.

Since $107 > B_{low}$, the root is not fathomed. There is no separate rule for choosing the branching variable. The algorithm always branches on the next undecided item in the efficiency-sorted order, here $x_1$. Item $1$ is not forced since $w_1=31 \le C=50$, so both $x_1=1$ and $x_1=0$ are explored, trying $x_1=1$ first.

$x_1=1$

Item $1$ is taken. $z=0+70=70$ and $C=50-31=19$. This branch is explored first, per the depth-first rule.

With item $1$ fixed, the remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 20x_2+39x_3+37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 10x_2+20x_3+19x_4+4x_5+3x_6+6x_7 \le 19 \ & \boldsymbol{x} \in {0,1}^6. \end{alignat*} $$ Dantzig's greedy algorithm packs item $2$ whole, since $w_2=10\le19$. Item $3$ no longer fits whole since $w_2+w_3=30>19$, so it is the critical item and gets the remaining capacity $19-10=9$ out of $w_3=20$. $$ p_2+p_3\cdot\frac{9}{20} = 20+39\cdot\frac9{20} = 37.55 $$ Flooring gives the residual Dantzig bound $U=37$, so $z+U=70+37=107$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $2$ is not forced since $w_2=10\le C=19$, so the algorithm branches on $x_2$, trying $x_2=1$ first.

$x_1=0$

Item $1$ is skipped. $z=0$ and $C=50$ unchanged. This branch is explored only after the entire $x_1=1$ subtree is fully resolved.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 20x_2+39x_3+37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 10x_2+20x_3+19x_4+4x_5+3x_6+6x_7 \le 50 \ & \boldsymbol{x} \in {0,1}^6. \end{alignat*} $$ Dantzig's greedy algorithm packs item $2$ whole, since $w_2=10\le50$, leaving capacity $40$. Item $3$ also packs whole, since $w_3=20\le40$, leaving capacity $20$. Item $4$ also packs whole, since $w_4=19\le20$, leaving capacity $1$. Item $5$ no longer fits whole since $w_5=4>1$, so it is the critical item and gets the remaining capacity $1$ out of $w_5=4$. $$ p_2+p_3+p_4+p_5\cdot\frac14 = 20+39+37+7\cdot\frac14 = 97.75 $$ Flooring gives the residual Dantzig bound $U=97$, so $z+U=0+97=97$. The final incumbent is $B_{low}=107$, and $97\le107$, so the node is fathomed here. No branch skipping item $1$ can beat the incumbent, and the search is complete.

$x_2=1$

Item $2$ is taken. $z=70+20=90$ and $C=19-10=9$. This branch is explored first, per the depth-first rule.

With items $1$ and $2$ fixed, the remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 39x_3+37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 20x_3+19x_4+4x_5+3x_6+6x_7 \le 9 \ & \boldsymbol{x} \in {0,1}^5. \end{alignat*} $$ Item $3$ alone already exceeds the capacity since $w_3=20>9$, so it is the critical item from the start and gets packed fractionally with the whole remaining capacity $9$ out of $w_3=20$. $$ p_3\cdot\frac{9}{20} = 39\cdot\frac9{20} = 17.55 $$ Flooring gives the residual Dantzig bound $U=17$, so $z+U=90+17=107$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $3$ cannot fit at all since $w_3=20>C=9$, so $x_3=0$ is forced.

$x_2=0$

Item $2$ is skipped. $z=70$ and $C=19$ unchanged. This branch is explored only after the $x_2=1$ subtree is fully resolved.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 39x_3+37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 20x_3+19x_4+4x_5+3x_6+6x_7 \le 19 \ & \boldsymbol{x} \in {0,1}^5. \end{alignat*} $$ Item $3$ alone already exceeds the capacity since $w_3=20>19$, so it is the critical item from the start and gets packed fractionally with the whole remaining capacity $19$ out of $w_3=20$. $$ p_3\cdot\frac{19}{20} = 39\cdot\frac{19}{20} = 37.05 $$ Flooring gives the residual Dantzig bound $U=37$, so $z+U=70+37=107$. The incumbent by this point is $B_{low}=105$, and $107>105$, so the node is not fathomed. Item $3$ cannot fit at all since $w_3=20>C=19$, so $x_3=0$ is forced.

$x_4=1$

Item $4$ is taken. $z=70+37=107$ and $C=19-19=0$.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 4x_5+3x_6+6x_7 \le 0 \ & \boldsymbol{x} \in {0,1}^3. \end{alignat*} $$ No capacity remains, so the residual Dantzig bound is $U=0$ and $z+U=107+0=107$. The incumbent is $B_{low}=105$, and $107>105$, so the node is not fathomed. Item $5$ cannot fit since $w_5=4>C=0$, so $x_5=0$ is forced.

$x_4=0$

Item $4$ is skipped. $z=70$ and $C=19$ unchanged. This branch is explored only after the $x_4=1$ subtree is fully resolved.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 4x_5+3x_6+6x_7 \le 19 \ & \boldsymbol{x} \in {0,1}^3. \end{alignat*} $$ All three remaining items now fit whole at once, since $w_5+w_6+w_7=4+3+6=13\le19$. $$ p_5+p_6+p_7 = 7+5+10 = 22 $$ All items fit exactly, so the residual Dantzig bound is already integer at $U=22$, giving $z+U=70+22=92$. The incumbent by this point is $B_{low}=107$, and $92\le107$, so the node is fathomed here. Even taking every remaining item cannot beat the incumbent.

Optimal solution

The search closes after visiting every node above. The incumbent improved three times, $102\to105\to107$, and no further branch can exceed $107$. $$ F(\boldsymbol{x}^) = 107, \qquad \boldsymbol{x}^ = (1,0,0,1,0,0,0) $$ This matches the root's Dantzig bound from Node 0 exactly, so the solution is provably optimal.

$x_3=0$ (forced)

Item $3$ is skipped. $z=70$ and $C=19$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 19x_4+4x_5+3x_6+6x_7 \le 19 \ & \boldsymbol{x} \in {0,1}^4. \end{alignat*} $$ Item $4$ fits whole exactly, since $w_4=19\le19$, leaving no capacity for any other item. $$ p_4 = 37 $$ The residual Dantzig bound is $U=37$, so $z+U=70+37=107$. The incumbent is $B_{low}=105$, and $107>105$, so the node is not fathomed. Item $4$ exactly fits the remaining capacity, so it is not forced either way, and both $x_4=1$ and $x_4=0$ are explored, trying $x_4=1$ first.

$x_3=0$ (forced)

Item $3$ is skipped. $z=90$ and $C=9$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 37x_4+7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 19x_4+4x_5+3x_6+6x_7 \le 9 \ & \boldsymbol{x} \in {0,1}^4. \end{alignat*} $$ Item $4$ alone already exceeds the capacity since $w_4=19>9$, so it is the critical item and gets packed fractionally with the whole remaining capacity $9$ out of $w_4=19$. $$ p_4\cdot\frac{9}{19} = 37\cdot\frac9{19} \approx 17.53 $$ Flooring gives the residual Dantzig bound $U=17$, so $z+U=90+17=107$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $4$ cannot fit either since $w_4=19>C=9$, so $x_4=0$ is forced.

$x_4=0$ (forced)

Item $4$ is skipped. $z=90$ and $C=9$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 7x_5+5x_6+10x_7 \ \text{s.t.}\quad& 4x_5+3x_6+6x_7 \le 9 \ & \boldsymbol{x} \in {0,1}^3. \end{alignat*} $$ Dantzig's greedy algorithm packs item $5$ whole, since $w_5=4\le9$, leaving capacity $5$. Item $6$ also packs whole, since $w_6=3\le5$, leaving capacity $2$. Item $7$ no longer fits whole since $w_7=6>2$, so it is the critical item and gets the remaining capacity $2$ out of $w_7=6$. $$ p_5+p_6+p_7\cdot\frac26 = 7+5+10\cdot\frac26 \approx 15.33 $$ Flooring gives the residual Dantzig bound $U=15$, so $z+U=90+15=105$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $5$ is not forced since $w_5=4\le C=9$, so the algorithm branches on $x_5$, trying $x_5=1$ first.

$x_5=1$

Item $5$ is taken. $z=90+7=97$ and $C=9-4=5$.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 5x_6+10x_7 \ \text{s.t.}\quad& 3x_6+6x_7 \le 5 \ & \boldsymbol{x} \in {0,1}^2. \end{alignat*} $$ Dantzig's greedy algorithm packs item $6$ whole, since $w_6=3\le5$, leaving capacity $2$. Item $7$ no longer fits whole since $w_7=6>2$, so it is the critical item and gets the remaining capacity $2$ out of $w_7=6$. $$ p_6+p_7\cdot\frac26 = 5+10\cdot\frac26 \approx 8.33 $$ Flooring gives the residual Dantzig bound $U=8$, so $z+U=97+8=105$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $6$ is not forced since $w_6=3\le C=5$, so the algorithm branches on $x_6$, trying $x_6=1$ first.

$x_5=0$

Item $5$ is skipped. $z=90$ and $C=9$ unchanged. This branch is explored only after the $x_5=1$ subtree is fully resolved.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 5x_6+10x_7 \ \text{s.t.}\quad& 3x_6+6x_7 \le 9 \ & \boldsymbol{x} \in {0,1}^2. \end{alignat*} $$ Both remaining items now fit whole. Item $6$ packs whole, since $w_6=3\le9$, leaving capacity $6$. Item $7$ also packs whole, since $w_7=6\le6$ exactly. $$ p_6+p_7 = 5+10 = 15 $$ Both items fit exactly, so no fractional item remains and the residual Dantzig bound is already integer at $U=15$. Then $z+U=90+15=105$. The incumbent is $B_{low}=102$, and $105>102$, so the node is not fathomed. Item $6$ is not forced since $w_6=3\le C=9$, so the algorithm branches on $x_6$, trying $x_6=1$ first.

$x_6=0$

Item $6$ is skipped. $z=97$ and $C=5$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 10x_7 \ \text{s.t.}\quad& 6x_7 \le 5 \ & x_7 \in {0,1}. \end{alignat*} $$ Item $7$ does not fit whole since $w_7=6>5$, so it is packed fractionally with the whole remaining capacity $5$ out of $w_7=6$. $$ p_7\cdot\frac56 \approx 8.33 $$ Flooring gives the residual Dantzig bound $U=8$, so $z+U=97+8=105$. The incumbent is now $B_{low}=102$, and $105>102$, so the node is not fathomed. Item $7$ cannot fit since $w_7=6>C=5$, so $x_7=0$ is forced.

$x_6=1$

Item $6$ is taken. $z=97+5=102$ and $C=5-3=2$.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 10x_7 \ \text{s.t.}\quad& 6x_7 \le 2 \ & x_7 \in {0,1}. \end{alignat*} $$ Item $7$ does not fit whole since $w_7=6>2$, so it is packed fractionally with the whole remaining capacity $2$ out of $w_7=6$. $$ p_7\cdot\frac26 = 10\cdot\frac26 \approx 3.33 $$ Flooring gives the residual Dantzig bound $U=3$, so $z+U=102+3=105$. This still exceeds $B_{low}=-\infty$, so the node is not fathomed. Item $7$ cannot fit since $w_7=6>C=2$, so $x_7=0$ is forced.

$x_7=0$ (forced)

Item $7$ is skipped. $z=102$.

All items are now decided and $z=102$ improves the incumbent, so $B_{low}=102$ with $\boldsymbol{x}=(1,1,0,0,1,1,0)$.

$x_7=0$ (forced)

Item $7$ is skipped. $z=97$.

All items are now decided, but $z=97$ does not improve the incumbent $B_{low}=102$, so this leaf is discarded.

$x_6=1$

Item $6$ is taken. $z=90+5=95$ and $C=9-3=6$.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 10x_7 \ \text{s.t.}\quad& 6x_7 \le 6 \ & x_7 \in {0,1}. \end{alignat*} $$ Item $7$ fits whole exactly, since $w_7=6\le6$, so the continuous relaxation just takes it whole and needs no fractional item. $$ p_7 = 10 $$ The residual Dantzig bound is $U=10$, so $z+U=95+10=105$. The incumbent is $B_{low}=102$, and $105>102$, so the node is not fathomed. Item $7$ exactly fits the remaining capacity, so it is not forced either way, and both $x_7=1$ and $x_7=0$ are explored, trying $x_7=1$ first.

$x_6=0$

Item $6$ is skipped. $z=90$ and $C=9$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 10x_7 \ \text{s.t.}\quad& 6x_7 \le 9 \ & x_7 \in {0,1}. \end{alignat*} $$ Item $7$ fits whole with capacity to spare, since $w_7=6\le9$, so the continuous relaxation just takes it whole. $$ p_7 = 10 $$ The residual Dantzig bound is $U=10$, so $z+U=90+10=100$. The incumbent is now $B_{low}=105$, and $100\le105$, so the node is fathomed here. No further branching is needed, since even taking every remaining item cannot beat the incumbent.

$x_7=1$

Item $7$ is taken. $z=95+10=105$ and $C=6-6=0$.

All items are now decided and $z=105$ improves the incumbent, so $B_{low}=105$ with $\boldsymbol{x}=(1,1,0,0,0,1,1)$.

$x_7=0$

Item $7$ is skipped. $z=95$.

All items are now decided, but $z=95$ does not improve the incumbent $B_{low}=105$, so this leaf is discarded.

$x_5=0$ (forced)

Item $5$ is skipped. $z=107$ and $C=0$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 5x_6+10x_7 \ \text{s.t.}\quad& 3x_6+6x_7 \le 0 \ & \boldsymbol{x} \in {0,1}^2. \end{alignat*} $$ No capacity remains, so the residual Dantzig bound is $U=0$ and $z+U=107+0=107$. The incumbent is $B_{low}=105$, and $107>105$, so the node is not fathomed. Item $6$ cannot fit since $w_6=3>C=0$, so $x_6=0$ is forced.

$x_6=0$ (forced)

Item $6$ is skipped. $z=107$ and $C=0$ unchanged.

The remaining subproblem is $$ \begin{alignat*}{3} \max_{\boldsymbol{x}}\quad& 10x_7 \ \text{s.t.}\quad& 6x_7 \le 0 \ & x_7 \in {0,1}. \end{alignat*} $$ No capacity remains, so the residual Dantzig bound is $U=0$ and $z+U=107+0=107$. The incumbent is $B_{low}=105$, and $107>105$, so the node is not fathomed. Item $7$ cannot fit since $w_7=6>C=0$, so $x_7=0$ is forced.

$x_7=0$ (forced)

Item $7$ is skipped. $z=107$.

All items are now decided and $z=107$ improves the incumbent, so $B_{low}=107$ with $\boldsymbol{x}=(1,0,0,1,0,0,0)$.