Reifying Global Constraints

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
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00737768
Contributor : Sylvain Soliman <>
Submitted on : Tuesday, October 2, 2012 - 3:52:17 PM
Last modification on : Monday, September 24, 2018 - 2:00:04 PM
Long-term archiving on : Friday, December 16, 2016 - 7:17:14 PM

File

RR-8084.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00737768, version 1

Collections

Citation

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

Share

Metrics

Record views

331

Files downloads

476