Embedding Propagators in a Concurrent Constraint Language

Autor: Tobias Müller and Jörg Würtz

Herausgeber:

Solving large and hard discrete combinatorial problems often requires the design of new constraints. Current constraint systems focus on either high-level modeling or efficient implementation technology. While each approach lacks the advantages of the other one, this paper describes the combination of them in the high-level concurrent constraint language Oz. We describe an interface to Oz providing abstractions to program new efficient constraints in CPP, preserving the benefits of Oz for problem modeling. While constraints and the Oz runtime system are linked through the interface, and adequate interface abstractions are supplied to implement advanced algorithmic techniques. In particular, it provides the means to reflect the validity of a constraint and to control and inspect the state of a constraint. This allows the user to solve demanding combinatorial problems, such as hard scheduling problems. It is desirable to execute concurrent constraint programs in parallel to profit from multiprocessor architectures. We discuss how the proposed interface can be adapted to parallel execution, avoiding the recoding of constraint implementations for sequential solvers.