| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2011-07-28 16:15 基数制約に対応するクラスタ向け並列SATソルバとその評価 ○徐 暁雋・山根裕二・上田和紀（早大）  DC2011-17 |
|
| 抄録 | （和） | 実問題から生成される構造的な問題に含まれる基数制約は,真理値のみを扱う SAT ソルバにとってボト ルネックとなる.そこで,基数制約を表し高速な伝播が可能な特殊節を加えた拡張 CNF を提案する.標準的な SAT ソルバの MiniSat 2.2 の推論フェーズと衝突による学習フェーズを改訂し特殊節に対応させ,より大規模な問題を解 くために並列化を行った.評価実験として,基数制約を含む時間割作成問題をベンチマークとして MiniSat 2.2 との 比較を行った. |
| （英） | Cardinality constraints generated from real-world problems are often a bottleneck of SAT solving. This paper proposes an extended CNF that can express cardinality constraints and allows high-performance unit prop- agation. We have implemented it on MiniSAT 2.2 which is one of the most popular SAT solvers,by improving deduction and propagation mechanisms to handle the extended CNF.Furthermore,we have parallelized it for larger-scale CNFs. To evaluate the performance improvement over the original MiniSAT,we made an experiment on our parallel extented solver using the ITC2007 benchmark set that contains cardinality constraints problems. | |
| キーワード | （和） | 基数制約 / 充足可能性問題 / 並列SATソルバ / 並列処理 / / / / |
| （英） | Cardinality Constraints / Satisfiability / Parallel SAT Solver / Parallelization / / / / | |
| 文献情報 | 信学技報, vol. 111, no. 164, DC2011-17, pp. 13-18, 2011年7月. | |
| 資料番号 | DC2011-17 | |
| 発行日 | 2011-07-21 (DC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | DC2011-17 |
|
| 研究会情報 | |
| 研究会 | DC CPSY |
| 開催期間 | 2011-07-28 - 2011-07-29 |
| 開催地（和） | かごしま県民交流センター |
| 開催地（英） | |
| テーマ（和） | 2011年並列／分散／協調処理に関する 『鹿児島』サマー・ワークショップ（SWoPP鹿児島2011） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | DC |
| 会議コード | 2011-07-DC-CPSY |
| 本文の言語 | 日本語 |
| タイトル（和） | 基数制約に対応するクラスタ向け並列SATソルバとその評価 |
| サブタイトル（和） | |
| タイトル（英） | A Parallel Extended SAT Solver for Cardinality Constraints |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 基数制約 / Cardinality Constraints |
| キーワード(2)（和/英） | 充足可能性問題 / Satisfiability |
| キーワード(3)（和/英） | 並列SATソルバ / Parallel SAT Solver |
| キーワード(4)（和/英） | 並列処理 / Parallelization |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 徐 暁雋 / XiaoJuan Xu / ジョ ギョウジュン |
| 第1著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山根 裕二 / Yuji Yamane / ヤマネ ユウジ |
| 第2著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 上田 和紀 / Kazunori Ueda / ウエダ カズノリ |
| 第3著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-07-28 16:15:00 |
| 発表時間 | 30分 |
| 申込先研究会 | DC |
| 資料番号 | DC2011-17 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.164 |
| ページ範囲 | pp.13-18 |
| ページ数 | 6 |
| 発行日 | 2011-07-21 (DC) |
[研究会発表申込システムのトップページに戻る]