Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Reifying Global Constraints

Francois Fages 1 Sylvain Soliman 1 
1 CONTRAINTES - Constraint programming
Inria Paris-Rocquencourt
Abstract : Global constraints were introduced two decades ago as a means to model some core aspects of combinatorial problems with one single constraint for which an efficient domain filtering algorithm can be provided, possibly using a complete change of representation. However, global constraints are just constraint schemas on which one would like to apply usual constraint operations such as reification, i.e. checking entailment, disentailment and negating the constraint. This is currently not the case in state-of-the-art tools and was not considered in the global constraint catalog until recently. In this paper, we propose a general framework for reifying global constraints and apply it to some important constraints of the catalog, such as the cumulative constraint for instance. We show that several global constraints that were believed to be hard to negate can in fact be efficiently negated, and that entailment and disentailment can be efficiently tested. We also point out some new global constraints that are worth studying from this point of view and provide some performance figures obtained with an implementation in Choco.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Tuesday, October 2, 2012 - 3:52:17 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:47 AM
Long-term archiving on: : Friday, December 16, 2016 - 7:17:14 PM


Files produced by the author(s)


  • HAL Id : hal-00737768, version 1



Francois Fages, Sylvain Soliman. Reifying Global Constraints. [Research Report] RR-8084, INRIA. 2012, pp.18. ⟨hal-00737768⟩



Record views


Files downloads