[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

Constraint satisfaction has traditionally been tackled by refinement search (domain-reduction techniques), which faced similar problems of exploiting high-level knowledge. The success of commercial tools like the ILOG Scheduler [PUBLink] can be ascribed mainly to their use of so-called global constraints. Régin [PUBLink] defines a global constraint as a substitute for a set of lower-level constraints, such that a more powerful domain-reduction algorithm can be applied. Using global constraints, constraint solvers can attain an enormous speedup and real-world application requirements can be satisfied.

For example, the alldifferent(V) constraint of the "send more money" example is a global constraint that forces all included variables of the set V to take different values. A formulation by lower-level constraints would include inequality constraints for all possible variable pairs of the set V. But the application of the global constraint with a specific data representation and satisfaction methods can yield much better performance (e.g., by a demon-observed array representation [PUBLink]).

The notion of global constraints can support local search approaches as well. It is transferred to a local search context in the following subsections.

• Global Constraints from a Local Search Perspective
• Internal Structures
• Improvement Heuristics

For questions, comments or suggestions, please contact us.

Last update:
September 24, 2001 by Alexander Nareyek