Explaining propagators for s-DNNF circuits

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

Smooth decomposable negation normal form (s-DNNF) circuits are a compact form of representing many Boolean functions, that permit linear time satisfiability checking. Given a constraint defined by an s-DNNF circuit, we can create a propagator for the constraint by decomposing the circuit using a Tseitin transformation. But this introduces many additional Boolean variables, and hides the structure of the original s-DNNF. In this paper we show how we can build a propagator that works on the s-DNNF circuit directly, and can be integrated into a lazy-clause generation-based constraint solver. We show that the resulting propagator can efficiently solve problems where s-DNNF circuits are the natural representation of the constraints of the problem, outperforming the decomposition based approach.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 9th International Conference, CPAIOR 2012, Proceedings
PublisherSpringer
Pages195-210
Number of pages16
ISBN (Print)9783642298271
DOIs
Publication statusPublished - 29 May 2012
Externally publishedYes
Event9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2012 - Nantes, France
Duration: 28 May 20121 Jun 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7298 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2012
CountryFrance
CityNantes
Period28/05/121/06/12

Cite this

Gange, G., & Stuckey, P. J. (2012). Explaining propagators for s-DNNF circuits. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 9th International Conference, CPAIOR 2012, Proceedings (pp. 195-210). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7298 LNCS). Springer. https://doi.org/10.1007/978-3-642-29828-8_13