Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Modelling Pearl with Sortedness Constraints
RISE, Swedish ICT, SICS, Computer Systems Laboratory.ORCID iD: 0000-0003-3079-8095
Show others and affiliations
2015 (English)Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2015, 9. p. 27-41
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-24472OAI: oai:DiVA.org:ri-24472DiVA, id: diva2:1043556
Conference
Global Conference on Artificial Intelligence
Projects
SICStus PrologAvailable from: 2016-10-31 Created: 2016-10-31 Last updated: 2018-08-24Bibliographically approved

Open Access in DiVA

fulltext(466 kB)26 downloads
File information
File name FULLTEXT01.pdfFile size 466 kBChecksum SHA-512
eb5132f58caab2d454e4fcdef633310cb7ca62b27ba42c19cee28163c5f3f213bc1c856926fd046f359bed46e2931e4540936bf22b5d80e92112bb7b95a41177
Type fulltextMimetype application/pdf

Other links

http

Authority records BETA

Carlsson, Mats

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
Computer Systems Laboratory
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 26 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 25 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.35.2