| 講演名 | 2005-04-18 MAX-2-SATに対する分枝限定法 古賀 祐一, 野々部 宏司, 柳浦 睦憲, 永持 仁, 茨木 俊秀, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | MAX-2-SATとは, n変数よりなるm個の節で各節のリテラル数が高々2であるものが与えられたとき, 充足節の重みの和を最大(すなわち非充足節の重み和を最小)にする変数の割当を求める問題であり, NP困難であることが知られている. MAX-2-SATに対しては, 近年, 分枝限定法を中心とする厳密解法への関心が高まっているが, 従来の研究では, 非充足節の重み和に対する下界値の優れた計算方法がなく, 多くの分枝操作を行って探索木を展開せざるをえなかった. 本研究では, 高精度の下界値を求めるアルゴリズムを二つ提案する. 両者とも同時には充足できない節の集合を表す有向グラフに基づいて計算を行う方法であり, 一方はMAX-2-SATを集合被覆問題に定式化して下界値計算を行う. これらの方法により, 従来の方法に比べて, 分枝限定法における探索木の節点数を大幅に減らすことに成功し, 多くの問題例に対して計算時間を短縮できることを計算実験によって確認した. |
| 抄録(英) | MAX-2-SAT is one of the representative combinatorial problems and it is known to be NP-hard. It is stated as follows : Given a set of m clauses involving n propositional variables, where each clause contains at most two literals, find a truth assignment that maximizes the total weight of satisfied clauses. For MAX-2-SAT, exact algorithms such as branch-and-bound method have been receieving much attention recently. However, to the best of our knowledge, there is no effective method for computing lower bounds on the total weight of unsatisfied clauses, resulting in a large number of nodes in the branch-and-bound search tree. In this paper, we propose two algorithms that compute lower bounds of high quality. Both are based on a directed graph that represents conflicts among clauses, and one of them uses a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as computation time. |
| キーワード(和) | 分枝限定法 / MAX-2-SAT / 集合被覆問題 |
| キーワード(英) | Branch-and-Bound / MAX-2-SAT / set covering problem |
| 資料番号 | COMP2005-3 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | MAX-2-SATに対する分枝限定法 |
| サブタイトル（和） | |
| タイトル（英） | Branch-and-Bound Algorithms for MAX-2-SAT |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分枝限定法 / Branch-and-Bound |
| キーワード(2)（和/英） | MAX-2-SAT / MAX-2-SAT |
| キーワード(3)（和/英） | 集合被覆問題 / set covering problem |
| 第 1 著者 氏名（和/英） | 古賀 祐一 / Yuichi KOGA |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 野々部 宏司 / Koji NONOBE |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 柳浦 睦憲 / Mutsunori YAGIURA |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 4 著者 氏名（和/英） | 永持 仁 / Hiroshi NAGAMOCHI |
| 第 4 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 5 著者 氏名（和/英） | 茨木 俊秀 / Toshihide IBARAKI |
| 第 5 著者 所属（和/英） | 関西学院大学理工学部 Department of Informatics, School of Science and Technology, Kwansei Gakuin University |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-3 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |