Paper Info
Title
The Cardinality Matrix Constraint
Abstract
Cardinality matrix problems are the underlying structure of several real world problems such as rostering, sports scheduling, and timetabling. These are hard computational problems given their inherent combinatorial structure. Constraint based approaches have been shown to outperform other approaches for solving these problems. In this paper we propose the cardinality matrix constraint, a specialized global constraint for cardinality matrix problems. The cardinality matrix constraint takes advantage of the intrinsic structure of the cardinality matrix problems. It uses a global cardinality constraint per row and per column and one cardinality (0,1)-matrix constraint per symbol. This latter constraint corresponds to solving a special case of a network flow problem, the transportation problem, which effectively captures the interactions between rows, columns, and symbols of cardinality matrix problems. Our results show that the cardinality matrix constraint outperforms standard constraint based formulations of cardinality matrix problems.
Year
DOI
Venue
2004
10.1007/978-3-540-30201-8_42
LECTURE NOTES IN COMPUTER SCIENCE
Keywords
Field
DocType
transportation problem
Discrete mathematics,Constraint satisfaction,Mathematical optimization,Computational problem,Computer science,Cardinal number,Matrix (mathematics),Constraint programming,Cardinality,Combinatorial optimization,Constraint logic programming
Conference
Volume
ISSN
Citations 
3258
0302-9743
16
PageRank 
References 
Authors
0.80
4
2
Name
Order
Citations
PageRank
Jean-charles Régin1131296.59
Carla P. Gomes22344179.21