On the Violation of Circuits in Decomposable Negation Normal Form

Lucas Bordeaux¹ and Nina Narodytska²

¹Microsoft Research Cambridge, UK
lucasb@microsoft.com

²NICTA and University of NSW, Sydney, Australia
ninan@cse.unsw.edu.au

Abstract. Local Search approaches to constraint satisfaction are based on the ability to compute violation scores. These estimate ’how far’ a given assignment is from satisfying the constraints, and aim at guiding the search towards assignments whose violation will, ultimately, be null. We study the computation of violation functions for Boolean predicates encoded in Decomposable Negation Normal Form, an important class of logical circuits that encode interesting constraints. We show that for these circuits an elegant and efficient violation function first proposed by Z. Stachniak is ”ideal” in a certain sense. We discuss more broadly the notion of ”ideal” violation and discuss the implications of this result.

LNAI 7691, p. 194 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012