Bibliographic Details
| Title: |
State-of-the-art Methods for Pseudo-Boolean Solving with SCIP |
| Authors: |
Mexi, Gioni, Kamp, Dominik, Shinano, Yuji, Pu, Shanwen, Hoen, Alexander, Bestuzheva, Ksenia, Hojny, Christopher, Walter, Matthias, Pfetsch, Marc E., Pokutta, Sebastian, Koch, Thorsten |
| Publication Year: |
2025 |
| Collection: |
Mathematics |
| Subject Terms: |
Mathematics - Optimization and Control |
| More Details: |
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. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2501.03390 |
| Accession Number: |
edsarx.2501.03390 |
| Database: |
arXiv |
