Conference Proceedings

Propagation=lazy clause generation

Olga Ohrimenko, Peter J Stuckey, Michael Codish, C Bessiere (ed.)

PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2007 | SPRINGER-VERLAG BERLIN | Published : 2007

Abstract

Finite domain propagation solvers effectively represent the possible values of variables by a set of choices which can be naturally modelled as Boolean variables. In this paper we describe how we can mimic a finite domain propagation engine, by mapping propagators into clauses in a SAT solver. This immediately results in strong nogoods for finite domain propagation. But a naive static translation is impractical except in limited cases. We show how we can convert propagators to lazy clause generators for a SAT solver. The resulting system can solve scheduling problems significantly faster than generating the clauses from scratch, or using Satisfiability Modulo Theories solvers with difference..

View full abstract