3
$\begingroup$

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?

  • 0
    Cross posted at http://cstheory.stackexchange.com/questions/14508/optimizations-for-tsp-problem-using-branch-and-bound2012-11-27
  • 0
    You 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 1