Academic Commons

Articles

{sets} -- A lightweight constraint programming language based on ROBDDs

Cohen, Haim; Edwards, Stephen A.

Constraint programming is a step toward ideal programming: you merely define the problem domain and the constraints the solution must meet and let the computer do the rest. Many constraint programming languages have been developed; the majority of them employ iterative constraint propagation over the problem variables. While such an approach solves many problems and can handle very rich data types, it is often too inefficient to be practical. To address this problem, we developed a constraint programming language called {sets} that uses reduced ordered binary decision diagrams (ROBDDs) as the solution engine. Providing a minimal syntax, the language can be used to solve many finite problems that fit the constraint programming paradigm. The minimal syntax and simple semantics of the language enable the user to create libraries customized for a specific problem domain. {sets} is particularly useful in problems where an efficient search algorithm yet know to exist or can not be developed due to time constraints. As long as the solution domain is finite and discrete, {sets} should be able to describe the problem and search for a solution. We describe the {sets} language through a series of examples, show how it is compiled into C++ code that uses a public-domain ROBDD library, and compare the performance of this language with other constraint languages.

Subjects

Files

Also Published In

Title
Proceedings of the IADIS International Conference on Applied Computing: Salamanca, Spain, 18-20 February 2007.

More About This Work

Academic Units
Computer Science
Publisher
International Association for Development of the Information Society
Published Here
September 22, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.