文献

J-GLOBAL ID：201902281813938519   整理番号：19A1934725

SAT問題を混合整数線形計画問題に変換する効率的方法【JST・京大機械翻訳】

An Efficient Method to Transform a SAT problem to a Mixed Integer Linear Programming Problem

著者 (6件)： Guo Wenxia (School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, P. R. China) ,  Wang Jin ,  He Majun ,  Ren Xiaoqin ,  Wang Qingxian ,  Tian Wenhong (Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing, P. R. China)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2018  号： ICCC  ページ： 1992-1996  発行年： 2018年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 文献におけるサブセット和問題(SSP)に対する3-SAT(充足可能性)問題を低減する方法が存在するが,それは小規模あるいは中規模問題に適用できるだけである。著者らの研究は,より大きなサイズにおける一般的SAT問題を二値整数線形計画法(BILP)問題に変換するための効率的な方法を見出すことである。SATにおける可変節制約の特徴を観察し,線形不等式モデル(LIM)を問題に適用し,3SATからサブセットSum問題(SSP)への縮小に基づくLIMSSATと呼ばれる方法を提案した。古典的なものとは異なり,新しい方法は,SSPの行列における要素として各ビットを扱い,それらの無い変数を持たないAとして集合行列を設定し,目標値としてbを,二値解としてxを設定する。したがって,著者らはxA≦bとしてモデルを構築した。実験結果は,新しい方法が数千の変数と節を持つ非常に大きなサイズの問題に対して効率的に動作し,最も良いSAT2016競争ベンチマークの一つによって試験された最良のソルバに匹敵する性能を持つことを示した。Copyright 2019 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *整数線形計画法 ,  部分集合 ,  ベンチマーク ,  不等式 ,  *線形性 ,  中規模
準シソーラス用語： ソルバ ,  目標値 , 【Automatic Indexing@JST】

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  パターン認識  (JE07000S)

タイトルに関連する用語 (2件)： SAT ,  整数線形計画