Branch And Bound Implementation for TSP in Java

Question

I wonder if there is a useful Java implementation of a Branch And Bound algorithm for the TSP or in general a OR framework which includes a BnB for TSP.

Thanks for your help!

Marco

Answer 1

BnB typically interacts with a complete sub-problem solver:

best_cost_soln_so_far = +inf
while (better_cost_soln = search_for_soln_cheaper_than(best_cost_soln_so_far))
{
    best_cost_soln_so_far = better_cost_soln
    backtrack_into_search
}

That is, your sub-problem search will backtrack whenever the cost of any partial solution it is exploring exceeds the bound set by best_cost_soln_so_far. If the sub-problem search does find a better solution, best_cost_soln_so_far is updated, and the search continues from where it left off, looking for a still better solution. It's pretty easy to implement.

That said, I doubt very much that you want to tackle large TSPs using complete search because of the huge search spaces involved; you may do better with approximate techniques such as simulated annealing.

Answer 2

I found this pdf. Its very helpful and has details example and java implementaion for Branch and bound For TSP Here is the File Link

Answer 3

OptaPlanner (open source, Java) has a Branch and Bound implementation. See the docs section about BaB specifically. The implementation of the algorithm starts from this class, but that's hard to follow.

It also has a TSP example: although not configured with BaB by default, it's trivial to do so, by adjusting tspSolverConfig.xml like this:

<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

There are extra optional parameters to control node sorting, node exploration manner, etc.

Answer 4

Although we all know that "Java and Javascript are similar like Car and Carpet are similar", I would recommend looking at SimplexJS which is a simple linear and MIP solver written in Javascript. Since it's small (less than 400 LOCs) it can be easily translated into Java. The author of the project also has a nice example of Solving TSPs with Integer Programming.