Implementation and Evaluation of
Advanced Propagation Algorithms for
Global Constraints

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
pdf (pdf 320 KB)
tar.bz2 (tar.bz2 144 KB)
Final talk 17.02.2005
pdf (pdf 692 KB)
tar.bz2 (tar.bz2 280 KB)
Report 08.02.2006
pdf (pdf 520 KB)
tar.bz2 (tar.bz2 404 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! Valid CSS!

$Date: 2007-05-26 15:14:15 +0200 (Sat, 26 May 2007) $ by Patrick Pekczynski