エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
TSP LP Lazy Subtour Elimination Constraints:巡回セールスマン問題 逐次組込制約による部分巡回路除去
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
TSP LP Lazy Subtour Elimination Constraints:巡回セールスマン問題 逐次組込制約による部分巡回路除去
前回はPulp(オープンソース最適化ソルバー/モデラー)を使ってTSP(巡回セールスマン問題)の厳密解をM... 前回はPulp(オープンソース最適化ソルバー/モデラー)を使ってTSP(巡回セールスマン問題)の厳密解をMTZ(Miller-Tucker-Zemlin)部分巡回路除去法で求めてみました。前々回に試したDP(動的計画法)よりはMTZのほうが高速でしたが、せいぜい数十ノード程度が限界でした。 Lazy Constraints(逐次組込制約): そして今回もLPで厳密解を求めますが、Lazy Constraintsという制約式を使ってみようと思います。Lazy Constraintsの日本語訳が検索してもあまりでてこないので(ここくらい)、逐次組込制約と呼ぶことにしました。あるいは切除平面法と呼ばれているのかもしれません。 Lazy Constraintsの特長として、最初に基本的な制約だけを与えて一度結果を出し、その結果からその都度必要な制約を追加していき、何回かのループで答えを出します。予