Branch & Bound TSP

For this assignment you will need working Graph and FromCSVFile implementations. Though FromCSVFile will not be directly by your implementation of the genetic algorithm, but will be used to test your code. Also, Set is going to be very useful, but is not required.

For this assignment, you will be implementing a branch & bound algorithm to compute the optimal solution to the TSP. You can see an academic paper on the algorithm here. See the pseudo-code in the paper listed under section 1.2 for details.

Functions

You will be implementing two different functions, though only one of them will have the actual implementation for branch & bound.

• BranchAndBoundTSPWithDefaultHeuristic - (yes a bit wordy) calls the other function with a default heuristic function provided. A closure would be a good way to implement the heuristic function.
• BranchAndBoundTSP - is the implementation of branch & bound, it uses a heuristic function to "prune" potential bad solutions.