Domain approximations for finite set constraint variables: An integrated approach

Patrick Pekczynski

Diploma Thesis at the Programming Systems Lab 2006,

Supervisor: Guido Tack

Responsible Professor: Prof. Gert Smolka

Timeframe: February 2006 - January 2007

Introduction

Constraint programming beyond finite integer domains is getting more and more attention, as witnessed by a great number of conference papers and a dedicated workshop. The most popular domain beyond integers is the domain of finite sets.
The predominant representation of domains for set constraint variables is to approximate a set with a greatest lower bound and a least upper bound, as introduced by Gervet [23]. Alternative representations include arrays of 0/1 variables or ordered binary decision diagrams [29]. Although many systems implement finite set constraints (for instance ILOG Solver [64], Mozart [48], ECLiPSe [52], and Choco [6]), little has been published about efficient data structures that implement finite set constraint variables.

Motivation

Data structures for constraint variable domains must be implemented very carefully, as their efficiency directly affects the efficiency of propagators operating on them, and thus the overall efficiency of the constraint system. For finite set constraints, no such analysis has been published.
Gecode [7], a generic constraint development environment, is designed to be open in the sense that new constraint domains can be added easily and efficiently. This makes it an ideal platform for experimenting with different implementations for finite set constraint variables.

Work packages

The thesis will comprise the following work packages:

Criteria of success

Further information

Introductory Talk Graduate Seminar PS 23.03.2006
pdf (pdf 400 KB)
tar.bz2 (tar.bz2 164 KB)
Final talk MPI AG1 seminar 12.02.2007
pdf (pdf 953 KB)
tar.bz2 (tar.bz2 422 KB)
2nd revision
Final talk Graduate seminar PS 21.03.2007
pdf (pdf 742 KB)
tar.bz2 (tar.bz2 321 KB)
1st revision
Diploma Thesis Submission 31.01.2007
pdf (pdf 663 KB)
tar.bz2 (tar.bz2 451 KB)

References

Complete list of references.

Note that links to ic-parc do not work as the center has been closed in 2005 (see https://www.imperial.ac.uk/spectrum/secretariat/ohrm/biogs/E000121b.htm ).



Valid XHTML 1.0 Strict Valid CSS!

Last change: $Date: 2007-05-26 15:06:01 +0200 (Sat, 26 May 2007) $ by Patrick Pekczynski