2025/01/06 by Gioni Mexi, Mexi, Gioni, Dominik Kamp +19 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #Formal Methods in Verification #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.2501.03390
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.