Reifying Global Constraints

Francois Fages (1) , Sylvain Soliman (1)

1 CONTRAINTES - Constraint programming

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.

Les contraintes globales ont été introduites il y a une vingtaine d'années afin de modéliser certains aspects centraux des problèmes combinatoires avec une seule contrainte dotée d'un algorithme de filtrage efficace, au besoin via un changement complet de représentation. Cependant, les contraintes globales ne sont que des schémas de contraintes sur lesquelles on souhaiterait pouvoir appliquer les opérations usuelles des contraintes comme la réification, ce qui suppose de tester l'implication et de nier la contrainte. Ceci n'est pas le cas dans les outils de l'état de l'art et n'a été considéré que récemment dans le catalogue des contraintes globales. Dans cet article nous proposons un cadre général pour réifier les contraintes globales, et l'appliquons aux principales contraintes du catalogue, comme par exemple la contrainte cumulative. Nous montrons que plusieurs contraintes réputées difficiles à nier peuvent l'être efficacement, et que l'implication peuvent être testée efficacement. Nous montrons aussi que de nouvelles contraintes globales vaudraient la peine d'être étudiées de ce point de vue, et fournissons une évaluation préliminaire des performances obtenues avec une implémentation en Choco.

Mots clés: Global constraints; reification; modelling

Domaines: Langage de programmation [cs.PL]

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