Solving Traveling
Salesman Problem with the Jicos branch &
bound framework
The application given below uses a trivial lower bound (weak &
simple to compute) and a trivial initial
upper bound (weak, requiring no computation).
It would be nice to improve these shortcomings, perhaps as an
"advanced"
section of the tutorial. I will do so as time permits.
The Jicos branch
& bound application of this tutorial consists
of the following classes, briefly described:
- constructs a TSP
instance as the computation's input
- constructs the initial upper
bound as
the shared object
- packages the computation's input
and
shared
object as Environment - they then are accessible to all tasks
- constructs this
branch and bound computation's root task
- gets a Remote
reference to an HSP
- logs in with the HSP
- gives the root task
to the HSP for processing
- receives the result
- logs out from the
HSP
- prints the minimal
cost tour that was returned, and its cost
- prints the HSP's
invoice, indicating the cost of using the HSP to
solve this problem.
- A class that is used
to construct a pseudo-random problem instance.
It only has a constructor, that:
- takes 3 arguments:
- the number of
nodes, n,
in the graph to be constructed
- the seed to be
used to start the pseudo-random number generation
- a maximum edge
weight.
- constructs an n
X n int
adjacency matrix with
random entries in the interval [ 0, max weight ).
The larger
the range of edge weights, the more likely it is that the graph has
many
pruning opportunities.
- prints the
adjacency matrix.
- TspSolution
implements jicos.application.branchandbound.Solution:
It is a class of [partial] solution objects for TSPs.
- Its data members
include:
- The size of the TSP
problem: the number of nodes in the graph to be
explored.
- The node that its
parent added to the current path.
- The node that it
added to the current path.
- The lower bound on
all solutions rooted at its parent node in the
search tree.
- The lower bound on
all solutions rooted its node in the search tree.
- A list of nodes,
called tour,
that are in the current path.
- A set of nodes,
called untour,
that are not yet in the path.
- Its 1-arg constructor
is used to construct only the initial
partial solution, which contains only the node 0 (the starting node) in
its
tour.
- It has the following
other methods:
- copy
- This method is used
to "construct" a template for the partial
solutions of the search nodes just below it in the search tree. It does
this
by "cloning" itself, and returning that as its value.
- computeLowerBound
- Computes the
lowerBound attribute for this partial solution.
It adds to the lowerBound (which is initialized to be the lowerBound of
its
parent) the distance from the parent's last node to its last node (the
last
edge added to the path).
- getChildren
- This method returns
a list of children solutions. It does
this as follows:
- For each node
that is not in the current tour it:
- creates a
partial solution;
- computes its
lower bound:
- if it is not
pruneable, it adds the child to its list of children
to return.
- returns the
generated list of children.
- getLowerBound
- returns the partial
solution's lower bound.
- isAtomic
- returns true if and
only if the search subtree is small enough
to be searched sequentially as a single task. The level at which the
subtree
is not further subdivided.
- isComplete
- returns true if and
only if the path is, in fact, a tour.
- toString
- prints the size of
the problem, the current path length, the
lower bound on all complete paths that include this as a subpath, and
the
list of nodes on the current path.
Discussion
Here
is the output, when we find the
minimum cost tour of a graph of 11 nodes, using 42 as the seed. |