I have to design a branch-and bound algorithm that solves the optimal tour of a graph on the cartesian plane every time. I have been given the hint that identifying hopeless branches earlier in the runtime will compound into a program that runs "a hundred times faster". I had the idea of assuming that the shortest edge connected to the starting/ending node will be either the first or last edge in the tour but a thin diamond shaped graph proves otherwise. Does any one have ideas for how to eliminate these hopeless branches or a reference that talks about this?
Optimizations for Travelling Salesman Problem
3
$\begingroup$
optimization
problem-solving
-
0You should only post on one site at a time. If an acceptable answer is not found there, then flag the moderators to migrate the question to another site. Please choose one site and delete the question from the others. – 2012-11-27
1 Answers
0
Are you allowed to use any kind of heuristic? If you have a heuristic that easily finds a feasible, yet not optimal tour, then you have a good bound for the tour. For example, in a given graph the optimal tour has length 100 miles (which is obviously not known beforehand). If you have a heuristic that finds a feasible tour with length say 500 miles, many branches in the branch and bound tree can be cut off by this upper bound. If the LP relaxation returns an optimal tour of length > 500 miles in a given part of the branch-and-bound tree, then the whole branch can be cut off as the integer solution cannot be better than the relaxation and we know that the optimal tour is less than or equal to 500 miles.