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

CREATORGioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu, Alexander Hoen, Ksenia Bestuzheva, Christopher Hojny, Matthias Walter, Marc E. Pfetsch, Sebastian Pokutta, Thorsten Koch
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03390

Browse the full library · About the Tower of Babel