ts問題を解決するためのブルートフォースや他のアルゴリズムと比較して、シンプレックス法はどれくらい速いですか？
2333 次
1 に答える
3
「純粋な」LP 問題 (連続変数を使用) で TS 問題をモデル化することはできません。研究ツリーの各ノードでシンプレックス法を使用する整数計画定式化を使用できます (分岐限定法または分岐切断法)。これは小さな問題では機能しますが、問題が難しいため遅くなります。たとえば、エッジごとに 1 つのバイナリ変数を使用すると、パスがサイクルであるという事実をモデル化するために多くの制約が必要になります。
ブルートフォースは扱いにくい (問題は指数関数的です) 。非常に小さな問題がない限り、試してはいけません。小さな問題であっても、MIP 定式化を使用します。
大きな問題の場合、ある種のヒューリスティック (シミュレートされたアニーリングはこれで良い結果をもたらすと思います) を使用するか、正確な解決策が必要な場合は問題の「スマートな」モデル化 (たとえば、列の生成) を使用する必要があります。
于 2012-12-06T07:37:59.120 に答える