文献

J-GLOBAL ID：201302236583983528   整理番号：13A0787327

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

On Composing the Simplex Method and Gomory Cut for Deriving Integer Assignments

著者 (5件)： 伏見政晃 (名古屋大 大学院情報科学研究科) ,  西田直樹 (名古屋大 大学院情報科学研究科) ,  酒井正彦 (名古屋大 大学院情報科学研究科) ,  草刈圭一朗 (名古屋大 大学院情報科学研究科) ,  坂部俊樹 (名古屋大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 457(MSS2012 59-86)  ページ： 109-114  発行年： 2013年02月27日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *シンプレックス法 ,  整数 ,  解 ,  合成 ,  *応用プログラム ,  有理数 ,  充足可能性問題 ,  *切除平面法 ,  不変性 ,  条件 ,  証明 ,  可能性 ,  *ソルバ
準シソーラス用語： *ゴモリーカット ,  決定可能性 ,  定理自動証明

分類 (2件)： 統計学  (AB08000H) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (4件)： 整数 ,  解 ,  導出 ,  単体法