State-of-the-art Methods for Pseudo-Boolean Solving with SCIP
Gioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu, Alexander Hoen, Ksenia Bestuzheva, Christopher Hojny, Matthias Walter, Marc E. Pfetsch, Sebastian Pokutta, Thorsten Koch · 2025
Read State-of-the-art Methods for Pseudo-Boolean Solving with SCIP by Gioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu, Alexander Hoen, Ksenia Bestuzheva, Christopher Hojny, Matthias Walter, Marc E. Pfetsch, Sebastian Pokutta, Thorsten Koch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03390.txt.
Description
Gioni Mexi and co-authors report how a general solver was tuned to win a contest on yes no choice problems, in a paper from 2025. Such problems mix straight and curved rules over true or false picks, with a best score or a full fit as the goal. In the 2024 contest the solver took five of the six classes it joined.
From more than twelve hundred test cases, the base solver cracked over seven hundred, and its twin run form cracked a few more. The team then pushed the solver still further on the back of those results. The paper lays out the tricks that won, from cut rules to search order, so peers can lift their own solvers for this hard class.
Catalog record
| CREATOR | Gioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu, Alexander Hoen, Ksenia Bestuzheva, Christopher Hojny, Matthias Walter, Marc E. Pfetsch, Sebastian Pokutta, Thorsten Koch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-03390