Skip to search boxSkip to navigationSkip to main content

A cardinality solver: More expressive constraints for free (Poster presentation)

  • Mark H. Liffiton(corresponding author)
    ,
  • Jordyn C. Maglalang
*Corresponding author for this work
Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Abstract

Despite the semantic simplicity of cardinality constraints, the CNF encodings typically used to solve them invariably turn one constraint into a large number of CNF clauses and/or auxiliary variables. This incurs a significant cost, both in space complexity and in runtime, that could be avoided by reasoning about cardinality constraints directly within a solver. Adding a single, native cardinality constraint instead of numerous clauses and/or auxiliary variables avoids any space overhead and simplifies the solver's procedures for reasoning about that constraint. Inspired by the simple observation that clauses are cardinality constraints themselves, and thus cardinality constraints generalize clauses, this work seeks to answer the question: How much of the research on developing efficient CNF SAT solvers can be applied to solving cardinality constraints?

Scholarship

Output type

Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Original language

English

Pages from-to (Number of pages)

Pages 485-486 (2 pages)

Publication milestones

  • Published - 2012

Publication status

Published - 2012

Publication series

  • Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print): 0302-9743
    ISSN (Electronic): 1611-3349
    Volume: 7317 LNCS
9783642316111

Publication IDs

  • Scopus: 84864236458

Host publication title

Theory and Applications of Satisfiability Testing, SAT 2012 - 15th International Conference, Proceedings