State-of-the-art Methods for Pseudo-Boolean Solving with SCIP
Authors:
- Gioni MexiGMGioni Mexi
- Dominik KampDKDominik Kamp
- Yuji ShinanoYSYuji Shinano
- Shanwen PuSPShanwen Pu
- Alexander HoenAHAlexander Hoen
- Ksenia BestuzhevaKBKsenia Bestuzheva
- Christopher HojnyCHChristopher Hojny
- Matthias WalterMWMatthias Walter
- Marc E. PfetschMPMarc E. Pfetsch
- Sebastian PokuttaSPSebastian Pokutta
- Thorsten KochTKThorsten Koch
Preprint
Abstract
The Pseudo-Boolean problem deals with linear or polynomial constraints with integer coefficients over Boolean variables. The objective lies in optimizing a linear objective function, or finding a feasible solution, or finding a solution that satisfies as many constraints as possible. In the 2024 Pseudo-Boolean competition, solvers incorporating the SCIP framework won five out of six categories it was competing in. From a total of 1,207 instances, SCIP successfully solved 759, while its parallel version FiberSCIP solved 776. Based on the results from the competition, we further enhanced SCIP's Pseudo-Boolean capabilities. This article discusses the results and presents the winning algorithmic ideas.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Efficient separation of RLT cuts for implicit and explicit bilinear termsMathematical Programming, 2024
- A unified framework for symmetry handlingMathematical Programming, 2024
- Computational aspects of infeasibility analysis in mixed integer programmingMathematical Programming Computation, 2021
- Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment ProblemMathematical Programming, 2019
- On the impact of running intersection inequalities for globally solving polynomial optimization problemsMathematical Programming Computation, 2019
- Generalized Totalizer Encoding for Pseudo-Boolean Constraints2015
- Orbital branchingMathematical Programming, 2009
- Packing and partitioning orbitopesMathematical Programming, 2007
- Mixed-integer bilinear programming problemsMathematical Programming, 1993
- Generalized resolution for 0?1 linear inequalitiesAnnals of Mathematics and Artificial Intelligence, 1992