The Conjunction of Interval AMONG Constraints

Gilles Chabert 1 Sophie Demassey 1
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
Abstract : An AMONG constraint holds if the number of variables that belong to a given value domain is between given bounds. This paper focuses on the case where the variable and value domains are intervals. We investigate the conjunction of AMONG constraints of this type. We prove that checking for satisfiability -- and thus, enforcing bound consistency -- can be done in polynomial time. The proof is based on a specific decomposition that can be used as such to filter inconsistent bounds from the variable domains. We show that this decomposition is incomparable with the natural conjunction of \textsc{Among} constraints, and that both decompositions do not ensure bound consistency. Still, experiments on randomly generated instances reveal the benefits of this new decomposition in practice. This paper also introduces a generalization of this problem to several dimensions and shows that satisfiability is NP-complete in the multi-dimensional case.
Type de document :
Communication dans un congrès
CPAIOR, 2012, Nantes, France. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00760044
Contributeur : Gilles Chabert <>
Soumis le : lundi 3 décembre 2012 - 13:10:57
Dernière modification le : jeudi 7 décembre 2017 - 01:24:56
Document(s) archivé(s) le : lundi 4 mars 2013 - 03:47:11

Fichier

paper31.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00760044, version 1

Collections

Citation

Gilles Chabert, Sophie Demassey. The Conjunction of Interval AMONG Constraints. CPAIOR, 2012, Nantes, France. 2012. 〈hal-00760044〉

Partager

Métriques

Consultations de la notice

314

Téléchargements de fichiers

109