Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T11:08:29.012Z Has data issue: false hasContentIssue false

Compiling finite domain constraints to SAT with BEE*

Published online by Cambridge University Press:  05 September 2012

AMIT METODI
Affiliation:
Department of Computer Science, Ben-Gurion University, Israel
MICHAEL CODISH
Affiliation:
Department of Computer Science, Ben-Gurion University, Israel
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present BEE, a compiler which enables to encode finite domain constraint problems to CNF. Using BEE both eases the encoding process for the user and also performs transformations to simplify constraints and optimize their encoding to CNF. These optimizations are based primarily on equi-propagation and on partial evaluation, and also on the idea that a given constraint may have various possible CNF encodings. Often, the better encoding choice is made after constraint simplification. BEE is written in Prolog and integrates directly with a SAT solver through a suitable Prolog interface. We demonstrate that constraint simplification is often highly beneficial when solving hard finite domain constraint problems. A BEE implementation is available with this paper.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2012