Patrick Pekczynski
Fopra at the
Programming Systems Lab SS 2004,
Supervisor:
Guido Tack
Responsible Professor:
Prof. Gert Smolka
Abstract
Constraint programming is a powerful technique for declaratively
solving hard combinatorial problems. There are several systems that
offer constraint programming, for example SICStus Prolog, ILOG Solver,
ECLiPSe, Mozart, and Gecode.
The two basic mechanisms of constraint programming that all these
systems build upon are constraint propagation and constraint
distribution. Constraint propagation is an efficient inference
mechanism obtained with concurrent propagators accumulating
information in a constraint store. Constraint distribution splits a
problem into complementary cases once constraint propagation cannot
advance further. By iterating propagation and distribution,
the system will eventually determine the solutions of a problem.
Usually, a distinction is made between "local" and "global"
constraints. Local constraints are more low-level, they are
independent and communicate only through the domains of shared
variables - examples are equality, less-than on finite integer domain
variables, or a subset constraint on finite set variables. Global
constraints are high-level constraints combining several local
constraints, exploiting global knowledge and hence yielding stronger
propagation. The most prominent example is the "alldifferent"
constraint that states that a set of finite domain integer variables
are pairwise disjoint.
Task
The aim of this project is the implemenation of the sortedness
constraint
that Sven Thiel developed
in his
PhD thesis, of a
permutation-based sortedness constraint as well as
the implemenation of the global cardinality constraint.
The implementation will be based on the
Gecode framework.
The novel propagator scheduling techniques present in Gecode
will be used and evaluated. The resulting system will be compared to other
implementations of the same constraints.
Further information
| Introductory Talk |
|
28.10.2004 |
|
|
|
| Final talk |
|
17.02.2005 |
|
|
|
| Report |
|
08.02.2006 |
|
|
|
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 ).
