Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On matrices, automata, and double counting in constraint programming
RISE., Swedish ICT, SICS, Computer Systems Laboratory.ORCID-id: 0000-0003-3079-8095
2013 (Engelska)Ingår i: Constraints, Vol. 18, s. 108-140Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M , with the same constraint C defined by a finite-state automaton A on each row of M and a global cardinality constraint "gcc" on each column of M . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the "gcc" constraints from the automaton A . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of M and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.

Ort, förlag, år, upplaga, sidor
Springer , 2013, 6. Vol. 18, s. 108-140
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:ri:diva-24089DOI: 10.1007/s10601-012-9134-yOAI: oai:DiVA.org:ri-24089DiVA, id: diva2:1043168
Projekt
SICStus PrologTillgänglig från: 2016-10-31 Skapad: 2016-10-31 Senast uppdaterad: 2018-08-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltexthttp

Personposter BETA

Carlsson, Mats

Sök vidare i DiVA

Av författaren/redaktören
Carlsson, Mats
Av organisationen
Computer Systems Laboratory
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 10 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
v. 2.35.10