2681. State-of-the-art Methods for Pseudo-Boolean Solving with SCIP
Invited abstract in session WB-43: Parallelize now!, stream Software for Optimization.
Wednesday, 10:30-12:00Room: Newlyn GR.07
Authors (first author is the speaker)
| 1. | Gioni Mexi
|
| Zuse Institute Berlin |
Abstract
The Pseudo-Boolean problem involves linear or polynomial constraints with integer coefficients over Boolean variables. The objective is to optimize a linear objective function, find a feasible solution, or maximize the number of constraints satisfied.
In the 2024 Pseudo-Boolean competition, solvers incorporating the SCIP framework won five of the six categories in which they competed. Out of a total of 1,207 instances, SCIP successfully solved 759, while its parallel version, FiberSCIP, solved 776.
In this talk, we discuss key modifications and new features implemented in SCIP to enhance its handling of Pseudo-Boolean problems. Moreover, we present the customized racing parallelization strategy used for FiberSCIP.
In our post-competition work, we extend SCIP with an infeasibility analysis based on cutting planes, inspired by conflict-driven solvers for Pseudo-Boolean optimization. Phrased in MIP terminology, this type of infeasibility analysis can be understood as a sequence of linear combinations, integer rounding operations, and cut generation. Our experimental results indicate that the new infeasibility analysis algorithm improves SCIP's performance on Pseudo-Boolean problems and on more general mixed-integer programs in terms of running time, number of nodes in the search tree, and the number of instances solved.
Keywords
- Programming, Integer
- Programming, Mixed-Integer
- Parallel Algorithms and Implementation
Status: accepted
Back to the list of papers