Finite Domain Constraints in Oz


The Idea

While finite domain constraints had an experimental status in Oz 1, Oz 2 now provides a rich set of propagators for the programmer. The performance of the system is consolidated and the functionality extended.

Tutorial Information

A first introduction to problem solving with finite domain constraints can be found in a draft section of An Oz Primer. The Oz programs are also available.

Structure of the module

The finite domain module has been restructured. This leads to the renaming of many propagators in the module FD. The structure is as follows.

Telling domains
Constrain variables to finite domains.
Reflection (FD.reflect)
Reflect information on variables.
Watching domains (FD.watch)
Watch the domain of variables.
Generic Propagators
Like the sum of an arbitrary number of variables.
Symbolic Propagators
Like the element constraint.
0/1 Propagators
Like the conjunction of two 0/1 variables.
Reified constraints (FD.reified)
Reification of constraints.
Miscellaneous Propagators
Like modulo constraint.
Scheduling (FD.schedule)
Support of scheduling functionality.
Distribution
Formerly called enumeration.

Support for scheduling

A variety of propagators and distribution strategies are dedicated to scheduling applications. These include techniques from Operations Research. Oz has been applied already to solve hard OR benchmarks in the area of job-shop scheduling as well as large problems coming from real-world applications. A workbench exists which allows to experiment with different scheduling strategies. More documentation on scheduling is in preparation.

Generic distribution

Distribution strategies can be easily written using a generic mechanism.

Non-linear constraints

Non-linear constraints are not delayed by default anymore.

Domain description

The domain descriptions can contain a complement operator compl now.

Further information

Further information on the new finite domain module can be found in a chapter of the Oz Standard Modules.


Jörg Würtz