Problem Description
Here's a program that demonstrates "Exhaustive" and "Branch and Bound"
search methods for finding the
best solution for "Knapsack" problems. It was adapted with author's kind
permission from the book "Ready-to-Run Delphi 3.0 Algorithms", Rod Stephens,
Wiley Computer Publishing.
Background & Techniques
The Knapsack Problem requires that we figuratively fill a knapsack by
selecting from a set of items whose
weight (or other "cost" measurement) and value (or "profit") are known.
The objective is to maximize the value (profit) of the items in the sack without
exceeding a predefined weight (cost) limit.
The "Exhaustive Search" method tries every combination of including or
excluding items to find the valid set with the largest value . For N
items, there are 2^{N} combinations because for each item
there are 2 choices; include the item or exclude this item. Actually,
we'll call it 2^{N }- 1 because the empty solution is not
really a solution. The possible combinations can be represented as a "binary tree" with the
each path from the starting "root" to the terminal "leaf" representing a unique
set of items. These paths or combinations can also be represented by the binary
notation of numbers from 0 to 2^N-1 . So, for example with 3 items, 8
combinations, the path
including items 1 and 2, but excluding item 3 could be represented by the number
6 (binary 110). Exhaustive search times for current PCs soon become unreasonable
when we have more than 30 items to choose from. The 30 item decision tree has about a billion possible
paths. My Dell Studio 17 Laptop checks about 50 million paths
per second so takes 20 seconds to solve the 30 item case. Each additional item
will double the number of paths to check and double the time to solve
by exhaustive search.
"Branch and bound" is an algorithm that significantly reduces the number of
combinations to be checked. It "prunes" the search tree" by aborting search
paths when they could not not possibly improve the best solution found to date. The program allows viewing the
process step by step here is a simple example:
Assume we have three items with [Cost, Profit] values of [30,8],
[25,4]. [40,3] and maximum cost of 50. Well start the
process down the right side of the tree by including item #1. The 4 paths
including item #1 are {#1}, {#1,#2}, {#1,#3} and {#1,#2,#3}. Adding
either item #2 or #3 would exceed our cost limit so out first "best" solution is
just item #1 with profit of 8. Now we have 3 paths left
to check, {#2}, {#2,#3} and {#3}. But before doing that we'll
do the Branch and Bound trick of checking the maximum profit if item #1 is
excluded. That number is the maximum profit if all items could be included
(15) minus the profit represented by the solution so far (8)
So the maximum profit from any path on the left side the tree is 7
(15 - 8 = 7). That number is less than our best profit so far (8), so no
need to check any of those paths and we are done! A example with 4 items
might be more convincing, but hard to explain. Run Branch and Bound
on a small case with the "Visualize steps" box checked for further study.
The Demo page is self explanatory. You can enter you own data or generate random
cases and solve them using either algorithm. The "Start" button will turn into a
"Stop" button during solving in case a problem is running longer than you care
to wait. For instructional purposes, you can see click the checkbox at the top
right of the form to follow the steps taken by Branch and Bound algorithm as it
finds the best solution. there are "Save and "Load" buttons in case you want to
preserve a case for future reference or for reporting a bug to me,
I want to thank author Rod Stephens for permission to use his program as the
basis for this one and for the book that helped me understand how it works.
The book is
"Ready-to-Run Delphi 3.0 Algorithms", Rod Stephens,
Wiley Computer Publishing. It was an experiment by Rod into Delphi as
a second (or third or fourth) language and he has since concentrated on Visual
Basic and C#. That's OK, I have investigated VB, (the best "other"
language for beginners IMO), but reverted to Delphi. Experienced
programmers typically have a "native" language as their language of choice.
Rod runs websites VB Helper (http://www.vb-helper.com)
and C# Helper (http://www.csharphelper.com)
where we might find items of interest to Delphians.
Running/Exploring the Program