On Matrices, Automata, and Double Counting

Nicolas Beldiceanu 1 Mats Carlsson 2 Pierre Flener 3 Justin Pearson 3
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
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.
Type de document :
Communication dans un congrès
Andrea Lodi and Michela Milano and Paolo Toth. 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, Jun 2010, Bologna, Italy. Springer, 6140, 2010, LNCS. 〈10.1007/978-3-642-13520-0_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00915717
Contributeur : Contraintes Lina <>
Soumis le : lundi 9 décembre 2013 - 11:52:18
Dernière modification le : vendredi 22 juin 2018 - 09:30:20

Lien texte intégral

Identifiants

Citation

Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Justin Pearson. On Matrices, Automata, and Double Counting. Andrea Lodi and Michela Milano and Paolo Toth. 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, Jun 2010, Bologna, Italy. Springer, 6140, 2010, LNCS. 〈10.1007/978-3-642-13520-0_4〉. 〈hal-00915717〉

Partager

Métriques

Consultations de la notice

170