A Modelling Pearl with Sortedness Constraints

Abstract : Some constraint programming solvers and constraint modelling languages feature the Sort(L, P , S ) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.
Type de document :
Communication dans un congrès
Global conference on artificial intelligence, Oct 2015, Tbilisi, Georgia. 2015, 〈http://easychair.org/smart-program/GCAI2015/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01186680
Contributeur : Contraintes Lina <>
Soumis le : mardi 25 août 2015 - 14:31:09
Dernière modification le : vendredi 22 juin 2018 - 09:32:42

Identifiants

  • HAL Id : hal-01186680, version 1

Citation

Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Xavier Lorca, Justin Pearson, et al.. A Modelling Pearl with Sortedness Constraints. Global conference on artificial intelligence, Oct 2015, Tbilisi, Georgia. 2015, 〈http://easychair.org/smart-program/GCAI2015/〉. 〈hal-01186680〉

Partager

Métriques

Consultations de la notice

423