Conference Proceedings

Lazy Clause Generation Reengineered

Thibaut Feydy, Peter J Stuckey, IP Gent

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

Abstract

Lazy clause generation is a powerful hybrid approach to combinatorial optimization that combines features from SAT solving and finite domain (FD) propagation. In lazy clause generation finite domain propagators are considered as clause generators that create a SAT description of their behaviour for a SAT solver. The ability of the SAT solver to explain and record failure and perform conflict directed back-jumping are then applicable to FD problems. The original implementation of lazy clause generation was constructed as a cut down finite domain propagation engine inside a SAT solver. In this paper we show how to engineer a lazy clause generation solver by embedding a SAT solver inside an FD ..

View full abstract