A Modelling Pearl with Sortedness Constraints

15 pages•Published: December 18, 2015

Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Xavier Lorca, Justin Pearson, Thierry Petit and Charles Prud'Homme

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.

Keyphrases: constraint decomposition, constraint modelling, constraint programming, constraint propagator, sortedness constraints, stable sort

In: Georg Gottlob, Geoff Sutcliffe and Andrei Voronkov (editors). GCAI 2015. Global Conference on Artificial Intelligence, vol 36, pages 27-41.

Links:	https://easychair.org/publications/paper/bXc
	https://doi.org/10.29007/b4dz

BibTeX entry

@inproceedings{GCAI2015:Modelling_Pearl_with_Sortedness,
  author    = {Nicolas Beldiceanu and Mats Carlsson and Pierre Flener and Xavier Lorca and Justin Pearson and Thierry Petit and Charles Prud'Homme},
  title     = {A Modelling Pearl with Sortedness Constraints},
  booktitle = {GCAI 2015. Global Conference on Artificial Intelligence},
  editor    = {Georg Gottlob and Geoff Sutcliffe and Andrei Voronkov},
  series    = {EPiC Series in Computing},
  volume    = {36},
  publisher = {EasyChair},
  bibsource = {EasyChair, https://easychair.org},
  issn      = {2398-7340},
  url       = {/publications/paper/bXc},
  doi       = {10.29007/b4dz},
  pages     = {27-41},
  year      = {2015}}

Download PDF Open PDF in browser