State-of-the-art Methods for Pseudo-Boolean Solving with SCIP

Alexander Hoen; Christopher Hojny; Dominik Kamp; Gioni Mexi; Ksenia Bestuzheva; Marc E. Pfetsch; Matthias Walter; Sebastian Pokutta; Shanwen Pu; Thorsten Koch

REVIEW

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2501.03390 v2 pith:LA3YOFL5 submitted 2025-01-06 math.OC

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

show 3 more authors

Marc E. Pfetsch Sebastian Pokutta Thorsten Koch

This is my paper

classification math.OC

keywords pseudo-booleanscipcompetitionconstraintsfindinglinearobjectiveresults

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original 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.

State-of-the-art Methods for Pseudo-Boolean Solving with SCIP

discussion (0)