Solving Traveling Salesman Problem with the Janet branch & bound framework

The Janet branch & bound application of this tutorial consists of the following classes, briefly described:

Application

• 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.

TSP

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

TSPSolution implements janet.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:

1. For each node that is not in the current tour it: 
1. creates a partial solution;
2. computes its lower bound:
3. if it is not pruneable, it adds the child to its list of children to return.
2. 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