Change search
ReferencesLink to record
Permanent link

Direct link
On Matrices, Automata, and Double Counting
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
Number of Authors: 4
2010 (English)Conference paper (Refereed)
Abstract [en]

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M, with the same constraint 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 evaluate the impact of our methods on a large set of nurse rostering problem instances.

Place, publisher, year, edition, pages
2010, 8. 10-24 p.
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-23774OAI: diva2:1042851
Seventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming
Lecture notes in computer science; 6140. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, 2010. Proceedings. Springer 2010Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

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

By organisation
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 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

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link