java - Java での TSP の分岐限定実装

Question

TSP 用の Branch And Bound アルゴリズム、または一般に 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

「Car と Carpet が似ているように、Java と Javascript は似ている」ことは誰もが知っていますが、Javascript で記述された単純な線形および MIP ソルバーであるSimplexJSを見ることをお勧めします。小さい (400 未満の LOC) ため、Java に簡単に変換できます。プロジェクトの作成者は、整数計画法で TSP を解決する良い例も持っています。