整数解を導出するための単体法とゴモリーカットの合成について

機関リポジトリ 機関リポジトリ (HANDLE) Web Site Web Site オープンアクセス

書誌事項

タイトル別名
  • セイスウカイ オ ドウシュツ スル タメ ノ タンタイホウ ト ゴモリーカット ノ ゴウセイ ニ ツイテ
  • On Composing the Simplex Method and Gomory Cut for Deriving Integer Assignments

この論文をさがす

説明

与えられた有理数上の線形制約を充足する割り当てを求める手法として単体法がある.また,有理数解を求める手法と,ゴモリーカットをはじめとする切除平面法を組み合わせることで整数解を求められることが知られている.しかし,単体法を適用した後,必ずしもゴモリーカットが適用可能であるとは限らない.本稿では,ゴモリーカットの合成に必要な単体法における不変条件を示し,単体法とゴモリーカットを合成した手続きを示す.また,ゴモリーカットで追加する制約について,より単純な実装を行うための制約の形式を述べる.これらに基づいて,上記2つの手法を合成したソルバを実装し,評価する.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ