Home

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

Haim Cohen; Stephen A. Edwards

Title:
{sets} -- A lightweight constraint programming language based on ROBDDs
Author(s):
Cohen, Haim
Edwards, Stephen A.
Date:
Type:
Articles
Department:
Computer Science
Permanent URL:
Book/Journal Title:
Proceedings of the IADIS International Conference on Applied Computing: Salamanca, Spain, 18-20 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 public-domain ROBDD library, and compare the performance of this language with other constraint languages.
Subject(s):
Computer science
Item views:
185
Metadata:
View

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services.