Definition · Branch and boundA search over partial solutions that, at each node, computes an upper bound on the best value any completion of that partial solution could have, and abandons the node when the bound does not beat the best complete solution found so far. The bound must never underestimate a completion, or the search may discard the optimum.
Theorem · The fractional relaxation is a valid boundLet a node have decided items 1 through i - 1, with value v taken and capacity c remaining. Then every completion of that node has value at most v plus the fractional knapsack optimum of items i through n with capacity c.
A
n
y
c
o
m
p
l
e
t
i
o
n
c
h
o
o
s
e
s
a
s
u
b
s
e
t
o
f
t
h
e
r
e
m
a
i
n
i
n
g
i
t
e
m
s
f
i
t
t
i
n
g
i
n
`
c
`
.
T
h
a
t
s
u
b
s
e
t
i
s
a
l
s
o
a
f
e
a
s
i
b
l
e
f
r
a
c
t
i
o
n
a
l
s
o
l
u
t
i
o
n
&
m
d
a
s
h
;
t
a
k
e
e
a
c
h
c
h
o
s
e
n
i
t
e
m
i
n
f
u
l
l
&
m
d
a
s
h
;
s
o
i
t
s
v
a
l
u
e
i
s
a
t
m
o
s
t
t
h
e
f
r
a
c
t
i
o
n
a
l
o
p
t
i
m
u
m
o
f
t
h
e
s
a
m
e
s
u
b
-
i
n
s
t
a
n
c
e
.
A
d
d
i
n
g
`
v
`
t
o
b
o
t
h
s
i
d
e
s
g
i
v
e
s
t
h
e
c
l
a
i
m
.
T
h
e
f
r
a
c
t
i
o
n
a
l
o
p
t
i
m
u
m
i
s
c
o
m
p
u
t
e
d
e
x
a
c
t
l
y
b
y
t
a
k
i
n
g
i
t
e
m
s
i
n
d
e
c
r
e
a
s
i
n
g
v
a
l
u
e
p
e
r
u
n
i
t
w
e
i
g
h
t
a
n
d
s
p
l
i
t
t
i
n
g
t
h
e
o
n
e
t
h
a
t
d
o
e
s
n
o
t
f
i
t
,
w
h
i
c
h
i
s
t
h
e
g
r
e
e
d
y
r
u
l
e
p
r
o
v
e
d
c
o
r
r
e
c
t
i
n
G
r
e
e
d
y
A
l
g
o
r
i
t
h
m
s
a
n
d
M
a
t
r
o
i
d
s
.
□
What the lab measured
The instance is the five items 3:5, 4:6, 5:8, 2:3, 6:9 with a capacity of 10. The panel reports a value of 16, the same 16 from an exhaustive search over 32 subsets, both searches correct, 14 nodes with the bound, 44 without, 32 for the whole tree, and 4 branches cut with the bound against 0 without. The optimum takes items 3:5, 5:8 and 2:3, filling the sack exactly at weight 10 for value 16.
At the root the fractional bound is 16, which is exactly the integer optimum on this instance. That is a coincidence of the numbers rather than a general fact, and it is worth noticing because it is the best case for a bound: it knows the answer before the search starts, and still has to prove it by exploring until every alternative is cut.
Example · The same code, a different instanceSwitch to the example with one heavy prize and a lot of filler — 9:30 and six copies of 1:2, capacity 9 — and the counts become 3 nodes with the bound against 135 without. The single item fills the sack, the fractional bound at the root is 30, taking it immediately gives 30, and everything else is cut at once. Switch to the example where every item has the same density and it is 30 against 86, with only 2 branches cut, even though the root bound of 26 is again exactly the optimum.
Those three instances are one algorithm and node counts of 14, 3 and 30. The ratio between bounded and unbounded search moves from about 3 to 45 to under 3, and the number of branches cut moves from 4 to 2 to 2 without tracking either. A tight bound at the root does not imply heavy pruning, because pruning compares the bound against the best answer found so far, and early in the search that is a poor answer.
What is therefore not established
Nothing about the worst case. Branch and bound on the knapsack is exponential in the worst case and the bound is not a complexity improvement — there are instances on which nothing is cut. What the node counts establish is what the bound bought on the instance in front of you, which is a real and useful fact about that instance and is the only kind of fact a counter can produce.
This is the first of the strategies and the one that gives up least: the answer is exact, the certificate is the search itself, and the cost is a number you can watch. Every later strategy trades some of that away — the guarantee of optimality, the range of instances, or the accuracy — and each trade is worth making only against a measurement like this one.