文献

J-GLOBAL ID：201802261137610943   整理番号：18A0333037

整数計画法問題のための不定等式制約の同定【Powered by NICT】

Identification of unidentified equality constraints for integer programming problems

著者 (1件)： Moeini Asghar. (School of Computer Science, Engineering and Mathematics, Flinders University, Tonsley Park, SA 5042, Australia)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 260  号： 2  ページ： 460-467  発行年： 2017年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 整数計画問題のすべての整数解を含む最小次元ポリトープの特性化非常に挑戦的な仕事である。しばしば,このタスクはすべての整数解が満たすべきことを線形等式制約を同定することにより促進される。典型的には,これらの制約のいくつかは容易に入手できるが,他はより技術的により発見される必要がある。本論文では,このような等式制約を得るためのモデラーを支援するための方法を開発した。新しい等式制約のセットは,唯一では無く,提案した方法は,基本的な問題の十分に大きな寸法のためのこれらの新しい等式制約の集合を生成することに注意すべきである。これら生成される制約条件は,根底にある問題の一般的な場合に対して容易に拡張した形のすることもあるし,あるいは一般化パターンは同定が困難なより複雑な形式である。後者の場合,パターン認識できる制約を検出するために開発された新しい混合整数プログラム。さらに,この混合整数プログラムは,モデラーは,特異的基準,1,0,および 1である係数を可能にする,または非ゼロ係数の数に限界を置くだけを満足する新しい制約であるかどうかを確認することを可能にする。提案した方法を説明するために,以前に発表された「塩基ポリトープ」を補完するために新しい等式制約のセットを導出した。続いて,これらの結果を利用して,いくつかの技術は整数計画問題を強化することを提案した。最後に,広く使用されているT SP(巡回セールスマン問題定式化の緩和は,互いに比較し,新たに発見された等式制約の助けを借りて強化される。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 定式化 ,  巡回セールスマン問題 ,  線形性 ,  キャラクタリゼーション ,  *整数計画法 ,  パターン認識
準シソーラス用語： ポリトープ ,  *等式制約 , 【Automatic Indexing@JST】

著者キーワード (5件)： 整数計画法 ,  凸包問題 ,  組合せ最適化問題 ,  拡張定式化 ,  巡回セールスマン問題

分類 (1件)： 数理計画法  (KA03030M)

タイトルに関連する用語 (4件)： 整数計画法 ,  問題 ,  等式制約 ,  同定