Generating Propagators for Finite Set Constraints

Speaker: Christian Schulte

Abstract:

Constraint programming is a successful and widely used method for solving combinatorial optimization problems. An essential ingredient for any constraint programming system are propagators implementing constraints performing strong constraint propagation.

Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator.

This talk introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. The approach taken is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, we transfer the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. We show soundness and completeness of the derived propagators and present a runtime analysis, including techniques for efficiently executing projectors for n-ary constraints.

Joint work with:

• Guido Tack, Programming Systems Lab, Saarland U, Germany
• Gert Smolka, Programming Systems Lab, Saarland U, Germany