Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

The SeqBin constraint revisited

Abstract : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

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

https://hal.inrae.fr/hal-02748668
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 13:56:51
Dernière modification le : vendredi 12 juin 2020 - 10:43:26

Fichier

The SEQBIN constraint revisite...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

14

Téléchargements de fichiers

41