onr:"swepub:oai:DiVA.org:kth-290612"
Search: onr:"swepub:oai:DiVA.org:kth-290612" > A cardinal improvem...
- 1 of 1
- Previous record
- Next record
- To hitlist
A cardinal improvement to pseudo-boolean solving
- Elffers, J. (author)
-
- Nordström, Jakob, 1972- (author)
- KTH,Teoretisk datalogi, TCS
- (creator_code:org_t)
- AAAI press, 2020
- 2020
- English.
- In: AAAI 2020 - 34th AAAI Conference on Artificial Intelligence. - : AAAI press. ; , s. 1495-1503
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- Pseudo-Boolean solvers hold out the theoretical potential of exponential improvements over conflict-driven clause learning (CDCL) SAT solvers, but in practice perform very poorly if the input is given in the standard conjunctive normal form (CNF) format. We present a technique to remedy this problem by recovering cardinality constraints from CNF on the fly during search. This is done by collecting potential building blocks of cardinality constraints during propagation and combining these blocks during conflict analysis. Our implementation has a non-negligible but manageable overhead when detection is not successful, and yields significant gains for some SAT competition and crafted benchmarks for which pseudo-Boolean reasoning is stronger than CDCL. It also boosts performance for some native pseudo-Boolean formulas where this approach helps to improve learned constraints. Copyright
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Artificial intelligence
- Cardinality constraints
- Clause learning
- Conflict analysis
- Conjunctive normal forms
- On the flies
- Potential building blocks
- Pseudo-Boolean
- SAT solvers
- Boolean algebra
Publication and Content Type
- ref (subject category)
- kon (subject category)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Elffers, J.
- Nordström, Jakob ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- AAAI 2020 - 34th ...
- By the university
- Royal Institute of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
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.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
