JavaにおけるTSPのブランチ・アンド・バインド実装

Question

TSP用のブランチ・アンド・バウンド・アルゴリズム、または一般に、TSP用のBnBを含むORフレームワークの有用なJava実装があるのだろうかと思います。

ありがとうございました！

マルコ

Answer 1

BnBのが一般的完全サブ問題解決者と対話：

それが模索されている任意の部分的な解決策のコストを超えた場合、あなたのサブ問題の検索がバックトラックされますされ

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 
} 

結合はbest_cost_soln_so_farによって設定されます。サブ問題検索がの場合、より良い解決策を見つけると、best_cost_soln_so_farが更新され、検索が中断していた場所から続行され、さらに良い解決策を探します。実装するのはかなり簡単です。

しかし、膨大な検索スペースが含まれているため、完全な検索を使用して大きなTSPに取り組みたいとは思っていません。シミュレートされたアニーリングなどのおおよそのテクニックを使用するとより効果的です。

Answer 2

私はすべて"Java and Javascript are similar like Car and Carpet are similar"を知っていますが、私はSimplexJSを見て、Javascriptで書かれた単純な線形MIPソルバーであることをお勧めします。小さな（400個未満のLOC）ので、簡単にJavaに変換できます。このプロジェクトの著者にはSolving TSPs with Integer Programmingという素晴らしい例もあります。

Answer 3

このpdfが見つかりました。その非常に便利で詳細な例とjavaのimplementaionブランチとバインドTSPのため Here is the File Link

Answer 4

OptaPlanner（オープンソース、Java）は、分岐とバインドの実装を持っています。 See the docs section about BaB specifically.アルゴリズムの実装はthis classから始まりますが、それは続くことは難しいです。

また、TSPの例があります。

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

ソートノードを制御するための追加オプションのパラメータがありますが、ノード探査：デフォルトでは、BABで構成されていないが、それはこのようtspSolverConfig.xmlを調整することで、そうするように些細です方法など