State-of-the-art Methods for Pseudo-Boolean Solving with SCIP
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916555727568896 |
|---|---|
| author | Mexi, Gioni Kamp, Dominik Shinano, Yuji Pu, Shanwen Hoen, Alexander Bestuzheva, Ksenia Hojny, Christopher Walter, Matthias Pfetsch, Marc E. Pokutta, Sebastian Koch, Thorsten |
| author_facet | Mexi, Gioni Kamp, Dominik Shinano, Yuji Pu, Shanwen Hoen, Alexander Bestuzheva, Ksenia Hojny, Christopher Walter, Matthias Pfetsch, Marc E. Pokutta, Sebastian Koch, Thorsten |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03390 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | State-of-the-art Methods for Pseudo-Boolean Solving with SCIP Mexi, Gioni Kamp, Dominik Shinano, Yuji Pu, Shanwen Hoen, Alexander Bestuzheva, Ksenia Hojny, Christopher Walter, Matthias Pfetsch, Marc E. Pokutta, Sebastian Koch, Thorsten Optimization and Control 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. |
| title | State-of-the-art Methods for Pseudo-Boolean Solving with SCIP |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.03390 |