Sökning: onr:"swepub:oai:DiVA.org:kth-238355" >
Using combinatorial...
Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers
-
- Elffers, Jan (författare)
- KTH,Teoretisk datalogi, TCS
-
- Giráldez-Cru, Jakob (författare)
- KTH,Teoretisk datalogi, TCS
-
- Nordström, Jakob, 1972- (författare)
- KTH,Teoretisk datalogi, TCS
-
visa fler...
-
- Vinyals, Marc (författare)
- Tata Institute of Fundamental Research, Mumbai, India
-
visa färre...
-
(creator_code:org_t)
- 2018-06-26
- 2018
- Engelska.
-
Ingår i: Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018. - Cham : Springer. - 9783319941431 ; , s. 75-93
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We study cdcl-cuttingplanes, Open-WBO, and Sat4j, three successful solvers from the Pseudo-Boolean Competition 2016, and evaluate them by performing experiments on crafted benchmarks designed to be trivial for the cutting planes (CP) proof system underlying pseudo-Boolean (PB) proof search but yet potentially tricky for PB solvers. Our experiments demonstrate severe shortcomings in state-of-the-art PB solving techniques. Although our benchmarks have linear-size tree-like CP proofs, and are thus extremely easy in theory, the solvers often perform quite badly even for very small instances. We believe this shows that solvers need to employ stronger rules of cutting planes reasoning. Even some instances that lack not only Boolean but also real-valued solutions are very hard in practice, which indicates that PB solvers need to get better not only at Boolean reasoning but also at linear programming. Taken together, our results point to several crucial challenges to be overcome in the quest for more efficient pseudo-Boolean solvers, and we expect that a further study of our benchmarks could shed more light on the potential and limitations of current state-of-the-art PB solving.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Annan teknik -- Övrig annan teknik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Other Engineering and Technologies -- Other Engineering and Technologies not elsewhere specified (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas