CODEWITHSUNDEEP
javaalgorithmtraveling-salesmanbranch-and-bound
user212926
user212926

Reputation:

Branch And Bound Implementation for TSP in Java

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

Upvotes: 3

Views: 6089

Answers (4)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

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.

Upvotes: 0

Alvi
Alvi

Reputation: 767

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

Upvotes: 1

vitaut
vitaut

Reputation: 55665

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.

Upvotes: 0

Rafe
Rafe

Reputation: 5295

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.

Upvotes: 2

Related Questions