Reifying Global Constraints

Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8084, INRIA. 2012, pp.18
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00737768
Contributeur : Sylvain Soliman <>
Soumis le : mardi 2 octobre 2012 - 15:52:17
Dernière modification le : samedi 17 septembre 2016 - 01:34:51
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 19:17:14

Fichier

RR-8084.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

326