{sets}  A lightweight constraint programming language based on ROBDDs

Title:

{sets}  A lightweight constraint programming language based on ROBDDs

Author(s):

Cohen, Haim
Edwards, Stephen A.

Date:

2007

Type:

Articles

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:11216

Book/Journal Title:

Proceedings of the IADIS International Conference on Applied Computing: Salamanca, Spain, 1820 February 2007.

Book Author:

Guimaraes, Nuno

Publisher:

International Association for Development of the Information Society

Publisher Location:

Lisbon

Abstract:

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 publicdomain ROBDD library, and compare the performance of this language with other constraint languages.

Subject(s):

Computer science
 Item views:

238
 Metadata:

text  xml
 Suggested Citation:

Haim Cohen, Stephen A. Edwards,
2007,
{sets}  A lightweight constraint programming language based on ROBDDs, Columbia University Academic Commons,
http://hdl.handle.net/10022/AC:P:11216.