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
On matrices, automata, and double counting in constraint programming
SICStus Prolog.
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
SICStus Prolog.
SICStus Prolog.
Number of Authors: 4
2013 (English)In: Constraints, Vol. 18, 108-140 p.Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Springer , 2013, 6. Vol. 18, 108-140 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-24089DOI: 10.1007/s10601-012-9134-yOAI: oai:DiVA.org:ri-24089DiVA: diva2:1043168
Projects
SICStus Prolog
Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp
By organisation
SICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 5 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.26.0