Boolean constraints in SWI-Prolog: A comprehensive system description

We present a new constraint solver over Boolean variables, freely available as library(clpb)1 in SWI-Prolog. In this paper, we explain the core algorithms and implementation trade-offs of our system. Our solver distinguishes itself from other available CLP(B) solvers by several unique features: First, it is written entirely in Prolog and is hence portable to other systems that provide a few interface predicates that we outline. Second, our system provides new interface predicates, and we show that they allow us to solve new types of problems with CLP(B) constraints. Finally, we present performance results and comparisons with the native CLP(B) solver of SICStus Prolog, and also with a new SICStus port of our system. Despite being written entirely in Prolog, both versions of our system can solve several benchmark instances that the native CLP(B) solver of SICStus Prolog cannot solve.