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:
- Empirical analysis, design and prototyping:
-
- Identification of the operations propagators perform on set
variables.
- Empirical assessment of the relative importance of the
individual operations.
- Design of an abstract data type for
representing set variables.
- Different implementations in the
Gecode framework, based on separate lower and upper bounds, a
unified data structure for both, or ROBDDs.
- Analytical and empirical comparison of the implemented data
structures.
- Implementation and evaluation of a set constraint solver based
on a complete representation of the domains using ROBDDs.
Criteria of success
- The work results in an efficient solver for set
constraint variables for the Gecode platform.
- The thesis presents a
careful analysis of the design decisions behind the implemented data
structures.
Further information
| Introductory Talk |
|
Graduate Seminar PS |
|
23.03.2006 |
|
|
|
| Final talk |
|
MPI AG1 seminar |
|
12.02.2007 |
|
|
|
|
|
2nd revision |
|
|
|
|
| Final talk |
|
Graduate seminar PS |
|
21.03.2007 |
|
|
|
|
|
1st revision |
|
|
|
|
| Diploma Thesis |
|
Submission |
|
31.01.2007 |
|
|
|
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 ).
