Scribd
Upload
307 views15 pages

0/1 Knapsack: Branch and Bound

The document discusses branch and bound, an algorithm used when greedy or dynamic programming cannot be applied. It is then applied to solve the 0/1 knapsack problem. Branch and bound uses a tree search approach, generating all children of the current node before exploring others. It prioritizes nodes using a ranking function to find optimal solutions faster. For knapsack, this involves relaxing restrictions to allow fractional weights initially to provide bounds, then searching tree branches in a best-first manner.

Uploaded by

Sushma Rani Vatekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
307 views15 pages

0/1 Knapsack: Branch and Bound

The document discusses branch and bound, an algorithm used when greedy or dynamic programming cannot be applied. It is then applied to solve the 0/1 knapsack problem. Branch and bound uses a tree search approach, generating all children of the current node before exploring others. It prioritizes nodes using a ranking function to find optimal solutions faster. For knapsack, this involves relaxing restrictions to allow fractional weights initially to provide bounds, then searching tree branches in a best-first manner.

Uploaded by

Sushma Rani Vatekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

0/1 KNAPSACK

BRANCH AND BOUND


BRANCH AND BOUND
• Branch and bound is more suitable for situations where
we cannot apply the greedy method and dynamic
programming.
• Usually, this algorithm is slow as it requires exponential
time complexities during the worst case, but sometimes it
works with reasonable efficiency.
The term branch-and-bound refers to all state space search methods in which
all children of the £-node are generated before any other live node can
become the £-node.

We have already seen two graph search strategies, BFS and D-search, in
which the exploration of a new node cannot begin until the node currently
being explored is fully explored.

Both of these generalize to branch-and-bound strategies.

In branch-and-bound terminology, a BFS-like state space search will be called


FIFO (First In First Out) search as the list of live nodes is a first-in-first-out list
(or queue).

A D-search•like state space search will be called LIFO (Last In First Out)
search as the list of live nodes is a last-in-first-out list (or stack).
The search for an answer node can often be
speeded by using an "intelligent" ranking
function, c(. ), for live nodes.
The next £-node is selected on the basis of
this ranking function.
Let T be a state space tree and c( ) a cost
function for the nodes in T. If X is a node in T then
c(X) is the minimum cost of any answer node in
the subtree with root X. Thus, c(T) is the cost of a
minimum cost answer node
0/1 knapsack problem using
Branch and Bound
The 0/1 knapsack problem
 Positive integer P1, P2, …, Pn (profit)
W1, W2, …, Wn (weight)
M (capacity)
n
maximize  Pi X i
i1
n
Xi = 0 or 1, i =1, …, n.
subject to  Wi X i  M
i1
The problem is
n modified:
minimize  P X
 i i
i1
53
The 0/1 knapsack problem

The Branching Mechanism in the Branch-and-Bound Strategy


to Solve 0/1 Knapsack Problem. 54
Ans: by quickly finding a feasible solution in a
greedy manner: starting from the smallest
available i, scanning towards the largest i’s until
M is exceeded. The upper bound can be
calculated.

55
How to find the ranking Function
 Ans: by relaxing our restriction from Xi = 0 or 1 to
0  Xi  1 (knapsack problem)
n
be an optimal solution for 0/1
Let   Pi Xi
i1 n
  Pi be an optimal
knapsack problem i1
and fractional knapsack
solution for Xi problem. Let
n n
Y=   Pi Xi , Y’   Pi
=
Xi .
i1
i1
YY’
By the best-first search scheme
That is, by expanding the node with the best
lower bound. If two nodes have the same lower
bounds, expand the node with the lower upper
bound.

57
Example (LCBB)
Consider the knapsack instance:
 n = 4;
(pi, p2,
p3, p4) = (10, 10, 12, 18);
 (wi. w2, w3, w4) = (2, 4, 6, 9) and
 M = 15.

You might also like