2 1996 Compulog Net Meeting on Parallelism and Implementation Technology

ffl It must be transparent to the user whether a propagator is implemented by an Oz program or by a C++ propagator implemented through the interface.

ffl The interface must support a propagator to have properties like statefulness, atomicity and efficient data structures. This is due to the requirements of the algorithms usually employed by propagators. Such algorithms are typically derived from techniques known from mathematics and Operations Research.

ffl Propagators and the Oz runtime-system are completely separated. They are glued together only by the interface abstractions. This enables the implementation of propagators without having access to the code of the Oz runtime-system.

ffl The programmer is freed from tedious tasks like suspending or waking up propagators and caring about computation spaces (see Section 2.1.). This is achieved by providing interface abstractions at an appropriate level.

Since we use C++, some similarities with the Ilog Solver are inevitable. The main difference is that in Ilog Solver both the problem formulation and the search strategy has to be written in C++. In contrast to Ilog Solver, Oz provides for performance-critical constraints the option to implement them more efficient as C++ propagators. The actual program is still an Oz program, i.e. the problem formulation and the embedding of the constraint problem in larger applications is done in a high-level language. Moreover, search itself and the labelling strategies can be programmed in Oz too.

C++ propagators are needed only in performance-critical Oz code segments. Oz is still useful for such code segments as a prototyping language. Code written in Oz can be efficiently debugged and tuned, before it is reimplemented using the interface. Our experiences shows that this approach shortens the development cycle of application programs.

The resulting finite domain system is expressive (it includes reified constraints [HW96], nonlinear constraints and several symbolic constraints) and more efficient than Oz 1.0 [ST95] with unseparated propagators, i.e. C++ propagators tightly integrated in the emulator. The viability of our approach is also exemplified by the incorporation of special-purpose propagators for scheduling [W?ur96]. The resulting system shows an efficiency comparable to Ilog Solver (see Section 5.). The plan of the paper is as follows. The next section sketches constraint computation in Oz and introduces basic notions and concepts. Section 3. explains in detail the implementation of a propagator, to give the reader an intuition of the expressiveness of the interface. A case study in Section 4. shows how more complex propagators benefit from the interface. Finally, the yielded results are presented and discussed.

2. Computation with Constraints in Oz

2.1. Computation Model

This paper focusses on constraints on finite sets of nonnegative integers, so-called finite domains, in the constraint programming language Oz. For a more thorough treatment see [SSW94, HW96, MW96]. For a detailed presentation of the programming model see [Smo95].

A basic constraint takes the form x = n, x = y or x 2 D, where x and y are variables, n is a nonnegative integer and D is a finite domain. The basic constraints reside in the constraint store. Oz provides efficient algorithms to decide satisfiability and implication for basic constraints.

For more expressive constraints, like x + y = z, deciding their satisfiability is not computationally tractable. Such non-basic constraints are not contained in the constraint store but are imposed