The SeqBin constraint revisited - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

The SeqBin constraint revisited

Résumé

We revisit the SEQBIN constraint [1]. This meta-constraint subsumes a number of important global constraints like CHANGE [2], SMOOTH [3] and INCREASINGNVALUE [4]. We show that the previously proposed filtering algorithm for SEQBIN has two drawbacks even under strong restrictions: it does not detect bounds disentailment and it is not idempotent. We identify the cause for these problems, and propose a new propagator that overcomes both issues. Our algorithm is based on a connection to the problem of finding a path of a given cost in a restricted n-partite graph. Our propagator enforces domain consistency in O(nd2) and, for special cases of SEQBIN that include CHANGE, SMOOTH and INCREASINGNVALUE in O(nd) time.
Fichier principal
Vignette du fichier
The SEQBIN constraint revisited_GK_1.pdf (495.58 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02748668 , version 1 (03-06-2020)

Identifiants

Citer

George Katsirelos, Nina Narodytska, Toby Walsh. The SeqBin constraint revisited. CP 2012 - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec, Canada. 1012p., ⟨10.1007/978-3-642-33558-7_26⟩. ⟨hal-02748668⟩
5 Consultations
24 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More