SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:kth-238355"
 

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
  • Konferensbidrag (refereegranskat)
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

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy