In this assignment you are to write a sequential C/C++ program for solving the traveling salesman problem. Specifically, for a set of input that represents a weighted undirected graph giving cities and distances of connections between cities, your program should output an optimal tour for the concerned traveling salesman, and the total cost such a tour will incur.
While the traveling salesman problem may be "easily" solved by considering all permutations of the cities, such an approach is often too costly. An improved strategy, coupled with the branch-and-bound technique, often produces the solution far more rapidly. In this strategy, we construct a state space tree by starting with a root that represents all tours. In this tree, each node has two children, and the tours that a node represents are divided by these children into two groups: those that have a particular edge and those that do not. The tree continues to be expanded until all possible tours are considered and the best is found.
In order to reduce the size of the state space tree, the branch and bound technique and some problem specific rules of inference should be employed as explained below.
To use branch and bound, some heuristics for computing a lower bound cost of all the tours that a node represents would be needed. As soon as the search identifies a tour, this lower bound would allow us to prune the entire subtree rooted at a node which has a lower bound cost >= the cost of this tour. The lower bounds may also be used as a heuristic for establishing a priority queue for node expansion.
There are various heuristics for establishing a lower bound of tours. For this assignment, the following rule may be used: "A tour in this context is a simple cycle consisting of all the cities in the given graph. Each city in a cycle is incident with two edges. Therefore, no tour can cost less than one half the sum over all cities v of the two lowest cost edges incident with v." In expanding the state space tree, each node is arrived at with a set of constraints that some edges must be included while others are to be excluded. These constraints alter our choices for the two lowest cost edges at each city. It is due to these constraints that the lower bound costs computed for each node in the state space tree will vary.
Each time we branch by considering the two children of a node in the state space tree, we need to examine if the inclusion or exclusion of the selected edge at that vantage point will lead to invalid tours.
If yes, the expansion of the tree through that branch can be terminated there. For example, if the node being expanded already included edges ab and ac, then the left child of this node at the next expansion that considers the inclusion of ad will lead to invalid tours. Therefore no expansion to the left child will take place.
For each child node that we generate through this expansion process, we compute its lower bound. If the lower bound for a child is as high, or higher than the lowest cost tour found so far, we can prune that child from the state space tree.