| Presentation | 2011-07-28 A Parallel Extended SAT Solver for Cardinality Constraints XiaoJuan XU, Yuji YAMANE, Kazunori UEDA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 propagation. 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Cardinality Constraints / Satisfiability / Parallel SAT Solver |
| Paper # | DC2011-17 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2011/7/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Dependable Computing (DC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Parallel Extended SAT Solver for Cardinality Constraints |
| Sub Title (in English) | |
| Keyword(1) | Cardinality Constraints |
| Keyword(2) | Satisfiability |
| Keyword(3) | Parallel SAT Solver |
| 1st Author's Name | XiaoJuan XU |
| 1st Author's Affiliation | Graduate School of Fundamental Science and Engineering, Waseda University() |
| 2nd Author's Name | Yuji YAMANE |
| 2nd Author's Affiliation | Graduate School of Fundamental Science and Engineering, Waseda University |
| 3rd Author's Name | Kazunori UEDA |
| 3rd Author's Affiliation | Faculty of Science and Engineering, Waseda University |
| Date | 2011-07-28 |
| Paper # | DC2011-17 |
| Volume (vol) | vol.111 |
| Number (no) | 164 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |