SODA

On Matrices, Automata, and Double Counting

Beldiceanu, Nicolas and Carlsson, Mats and Flener, Pierre and Pearson, Justin (2010) On Matrices, Automata, and Double Counting. In: Seventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming, 14-18 June 2010, Bologna, Italy.

[img]
Preview
PDF
237Kb

Abstract

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.

Item Type:Conference or Workshop Item (Paper)
Additional Information: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 2010
ID Code:4051
Deposited By:Vicki Carleson
Deposited On:16 Dec 2010 13:05
Last Modified:16 Dec 2010 13:05

Repository Staff Only: item control page