| Presentation | 2021-01-27 Speeding up combinatorial optimization solver CombSQL+ by introducing Pseudo-Boolean constraints Junichiro Kishi, Masahiko Sakai, Naoki Nishida, Kenji Hashimoto, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The authors have proposed a solver CombSQL+ for combinatorial optimization problems (COPs) described in extended SQL language. The system generates QFLIA constraints by executing an SQL query transformed from an input description, and then solves them by an SMT solver. This report proposes an improvement of the system to generate constraints in pseudo-Boolean forms if possible. We report that the enhancement accelerates more than seven times faster for a problem. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Combinatorial optimization / SQL / SAT / SMT / pseudo-Boolean constraint |
| Paper # | MSS2020-40,SS2020-25 |
| Date of Issue | 2021-01-19 (MSS, SS) |
| Conference Information | |
| Committee | MSS / SS |
|---|---|
| Conference Date | 2021/1/26(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Shigemasa Takai(Osaka Univ.) / Takashi Kobayashi(Tokyo Inst. of Tech.) |
| Vice Chair | Atsuo Ozaki(Osaka Inst. of Tech.) / Kozo Okano(Shinshu Univ.) |
| Secretary | Atsuo Ozaki(Setsunan Univ.) / Kozo Okano(Hokkaido Univ.) |
| Assistant | Naoki Hayashi(Osaka Univ.) / Shinpei Ogata(Shinshu Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Software Science |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Speeding up combinatorial optimization solver CombSQL+ by introducing Pseudo-Boolean constraints |
| Sub Title (in English) | |
| Keyword(1) | Combinatorial optimization |
| Keyword(2) | SQL |
| Keyword(3) | SAT |
| Keyword(4) | SMT |
| Keyword(5) | pseudo-Boolean constraint |
| 1st Author's Name | Junichiro Kishi |
| 1st Author's Affiliation | Nagoya University(Nagoya univ.) |
| 2nd Author's Name | Masahiko Sakai |
| 2nd Author's Affiliation | Nagoya University(Nagoya univ.) |
| 3rd Author's Name | Naoki Nishida |
| 3rd Author's Affiliation | Nagoya University(Nagoya univ.) |
| 4th Author's Name | Kenji Hashimoto |
| 4th Author's Affiliation | Nagoya University(Nagoya univ.) |
| Date | 2021-01-27 |
| Paper # | MSS2020-40,SS2020-25 |
| Volume (vol) | vol.120 |
| Number (no) | MSS-342,SS-343 |
| Page | pp.pp.66-71(MSS), pp.66-71(SS), |
| #Pages | 6 |
| Date of Issue | 2021-01-19 (MSS, SS) |