SODA

On matrices, automata, and double counting in constraint programming

Beldiceanu, Nicolas and Carlsson, Mats and Flener, Pierre and Pearson, Justin (2013) On matrices, automata, and double counting in constraint programming. Constraints, 18 (1). pp. 108-140.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/s10601-012-9134-y

Abstract

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.

Item Type:Article
ID Code:5350
Deposited By:Mats Carlsson
Deposited On:17 Jan 2013 11:42
Last Modified:17 Jan 2013 11:42

Repository Staff Only: item control page