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

doi:10.48550/arXiv.2501.03390

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

^*Corresponding author for this work

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

5 Downloads (Pure)

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.

Original language	English
Publisher	ArXiv.org
Number of pages	20
DOIs	https://doi.org/10.48550/arXiv.2501.03390
Publication status	Published - 6 Jan 2025

Keywords

math.OC

Access to Document

10.48550/arXiv.2501.03390Licence: CC BY

2501.03390v2Final published version, 259 KBLicence: CC BY

Cite this

@techreport{ac63dabcd9d34601baa764c6ebd38a96,

title = "State-of-the-art Methods for Pseudo-Boolean Solving with SCIP",

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 = "math.OC",

author = "Gioni Mexi and Dominik Kamp and Yuji Shinano and Shanwen Pu and Alexander Hoen and Ksenia Bestuzheva and Christopher Hojny and Matthias Walter and Pfetsch, {Marc E.} and Sebastian Pokutta and Thorsten Koch",

year = "2025",

month = jan,

day = "6",

doi = "10.48550/arXiv.2501.03390",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

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

AU - Mexi, Gioni

AU - Kamp, Dominik

AU - Shinano, Yuji

AU - Pu, Shanwen

AU - Hoen, Alexander

AU - Bestuzheva, Ksenia

AU - Hojny, Christopher

AU - Walter, Matthias

AU - Pfetsch, Marc E.

AU - Pokutta, Sebastian

AU - Koch, Thorsten

PY - 2025/1/6

Y1 - 2025/1/6

N2 - 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.

AB - 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.

KW - math.OC

U2 - 10.48550/arXiv.2501.03390

DO - 10.48550/arXiv.2501.03390

M3 - Preprint

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

PB - ArXiv.org

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this