| Image
Processing Articles
Index |
 |
| What
is Branch and Bound
Algorithm? |
| These
notes follow the discussion
of branch and bound
algorithms in Computer
Algorithms by E. Horowitz,
S. Sahni and S. Rajasekaran. |
|
| Here
we describe a mathematical
model of the process
of choosing the next
node to expand. This
model also includes
a function for deciding
when to abandon a
search path before
reaching the end of
the path. Abandoning
searches early attempts
to minimize computational
efforts to find the
minimal solution. |
|
| The
basis of branch and
bound algorithms is
a ranking function.
The ranking function
assigns a value to
each node in the graph.
At each step, a branch
and bound algorithm
uses the ranking function
to decide which node
to expand next. In
contrast, the usual
DFS (Depth First Search)
and BFS( Breadth First
Search) exploration
algorithms perform
a blind search of
the graph. Ideally,
the ranking function,
c(x), ranks nodes
based on the cost
of a minimal solution
reachable from node
x. The problem with
this ranking function
is that the minimal
solution must be known
ahead of time. Instead,
the ranking function
uses an estimate,
g(x), of the cost
of a minimal solution
reachable from node
x. Using g(x) to rank
nodes may require
exploring unnecessary
nodes in the graph—particularly
if g(x) is not a good
estimate.The final
element of the ranking
function measures
the cost of reaching
a node from the root.
As the searches gets
farther from the root
node, the node falls
in the ranking. |
|
| The
function h(x) measures
the cost of reaching
node x from the root
node. After including
a function of h(x),
the ranking function
c(x) is |
|
| c(x)
= f(h(x)) + g(x) |
|
| in
which f determines
how much significant
to give the cost of
reaching node x. If
f(h(x))= 0 then the
algorithm makes long,
deep searches of the
graph. If f(h(x))>
0 then the algorithm
considers nodes close
to the root before
making long potentially
fruitless forays into
the graph. A node
is live if its subgraph
might contain a minimal
solution. Live nodes
are potential candidates
for exploration. A
node is dead if its
subgraph can not contain
a minimal solution.
If the estimated cost
of a minimal solution
reachable from x is
less than the actual
minimal solution reachable
from x then a node
can be killed when
the estimated cost
is greater than the
least upper bound
on a solution. In
symbols, if c(x)>=
upper then an optimal
solution is not reachable
from x (assuming upper
is the least upper
bound on a solution).It
should come as no
surprise that tuning
c by adjusting f and
g requires empirical
studies of representative
data sets. |
|
| 1-Traveling
Salesperson Problem |
| Two
branch and bound solutions
to the TSP are described
in this section. Each
solution estimates
the cost of a minimal
tour using a reduced
cost matrix. In the
first solution, the
nodes in a path through
the search tree represent
cities on a tour.
In the second solution,
nodes in the search
tree represent the
inclusion or exclusion
of an edge between
two cities in the
optimal tour. Suppose
the distances between
n cities are given
in an nxn matrix.
A row (or column)
in this matrix is
reduced if at least
one entry in the row
is 0 while the others
are all positive.
A matrix is reduced
if all of its rows
are reduced. |
|
| For
a non-leaf node S
with parent R, the
cost of a tour including
a trip from R to S
can be estimated by
a reduced cost matrix
A. Matrix A is constructed
by: |
|
| 1.
set all entries of
row R and column S
to 1 to avoid making
a second visit to
R or S in an optimal
tour. |
|
| 2.
set A(S, 1) to ∞ to
prevent making a premature
trip from S to 1. |
|
| 3.
For each row or column
that does not contain
all 1, subtract each
entry in each row
by the smallest value
in each row. Subtract
each entry in each
column by the smallest
value in each column.The
estimated length of
the shortest tour
including a trip from
R to S is given by: |
|
| c(S)
= f(h(R) + 1) + c(R)
+ A(R, S) + r |
|
| where
r is the total value
subtracted in step
3. The optimal values
of f and h are determined
empirically. |
|
| In
its solution, trees
were built by deciding
which node to visit
next. For example,
the nodes in the ith
level of the graph
are the options for
the ith city in a
tour. Another solution
can be built by deciding
whether or not to
include a trip between
a particular pair
of cities in each
step. In this solution,
the 2 root node might
represent the decision
to include or non-include
a trip between cities
6 and 8. The left
child represents the
inclusion this trip
and the right child
represents the exclusion
of this trip. The
same distance cost
estimate function
c is used in this
solution. The efficient
implementation of
this algorithm requires
a policy for choosing
which trip between
cities to consider
next in the search.
A good policy is to
choose cities R, S
such that a trip between
R and S has a high
probability of being
included in the optimal
tour. One way of choosing
R and S is to choose
cities which result
in the highest approximate
cost for not including
a trip between R and
S in the tour. |
|
| C#
Sample Program: |
|
| The
algorithm is coded
in C# using the Data
adapters and data
sets for accessing
databases for reading
and writing sales
person's visited cities
and their costs with
different problem
IDs. There is a set
of modules that are
designed to implement
the Branch and Bound
algorithm. The program
is designed so that
it takes input from
a database named "tsp.mdf"
with the path "C:/tsp.mdf".
The "tProblems"
table contains the
problem information
and the "tMatrics"
table contains the
matrices that contain
the cost of traveling
between each pair
of cities. The tables
have the following
structure: |
|
| tProblems |
| Field |
Type |
Comments |
| key |
Number |
|
| ProblemID |
Integer |
Identifier
for this problem
in the tMatrices
and tSolutions
tables. |
| Cities |
Integer |
Number
of cities in
this problem. |
| TimeBound |
Float |
How
many seconds
allowed for
solving this
problem. |
|
|
| tMatrices |
| Field |
Type |
Comments |
| key |
Number |
|
| Problem |
Integer |
Identifier
for this problem,
matches problemID
in tPRoblems.
|
| Row |
Integer |
Which
row of the cost
matrix is this
row of the table? |
| Contents |
String |
Space-separated
list of costs. |
|
|
| Implementation |
| The
branch and bound algorithm
is implemented to
solve the tsp problem
within the given time
bound. If time expires
before the algorithm
finds a solution,
then the program returns
the best solution
found so far and exit. |
|
| Output |
| The
output is written
to a table called
tSolutions. This table
has the following
fields: |
|
| tSolutions |
| Field |
Type |
Comments |
| key |
Number |
This
is automatically
updated, you
can ignore it |
| Problem |
Integer |
Identifier
for this problem,
matches problemID
in tPRoblems.
|
| Cost |
Integer |
Cost
of your solution. |
| Path |
String |
Order
in which you
visited the
cities in your
solution. Start
with the city
in the first
row. Name the
cities A, B,
C, ... Z, a,
b, ... z where
the city in
the first row
is A, the city
in the second
row is B and
so forth. |
| ExactSolution |
Boolean |
Was
your solution
exact? |
| TimeSpent |
Float |
Amount
of time your
algorithm spent
solving this
problem. If
you run out
of time, it
is ok for this
value to be
slightly larger
than the time
bound (because
you probably
won't check
the time between
every pair of
instructions
and you will
need a little
time to turn
off your timer
and output the
solution). |
|
|
Download
Project Files
 |
|
| Image
Processing Articles
Index |
