traveling-salesman - Concorde TSP ソルバーに制約を追加する方法

Question

巡回セールスマン問題の修正版を解こうとしています。これは基本的な TSP の修正であり、すべてのノードが色のプロパティを持ち、最適なパスが同じ色の 4 つを超えるノードに連続して接触することはできません。これは、100 ノード以下の接続グラフで実行されます。Concordeを使用してこれを実行しようとしています。

コンコルドの実行に色の制約を追加する方法を知っている人はいますか?

ありがとう

Answer 1

Concorde が任意の制約を追加するように設定されているとは思いません。ソルバーは従来の TSP 用に高度にカスタマイズされており、そのような新しい制約に対応できません。それを行う唯一の方法は、(制約ではなく) データのみを変更することによって、つまり、最適なコスト マトリックスを設定するためのトリックを考え出すことによって、問題を従来の TSP に変換する方法を見つけられる場合です。ソリューションは常に色の制約を満たしますが、それを行う方法がわかりません。