Branch And Bound Implementation for TSP in Java

I wonder if ther开发者_运维技巧e 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

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.

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

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.

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.