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.
Supported by the Intelligent Information Systems Institute, Cornell University (AFOSR grant F49620-01-1-0076) and EOARD grant FA8655-03-1-3022.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)
Berge, C.: Graphe et Hypergraphes. Dunod, Paris (1970)
DinchaK, M., Simonis, H., Van Hentenryck, P.: Solving the car-sequencing problem in constraint logic programming. In: ECAI 1988, proceedings of the European Conference on Artificial Intelligence, pp. 290–295 (1988)
Dotu, I., del Val, A., Cehrian, M.: Redundant modeling for the quasigroup completion problem. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 288–302. Springer, Heidelberg (2003)
Easton, K., Ncmhauscr, G., Trick, M.: Sports scheduling. In: Leung, J. (ed.) Handbook of Scheduling: Models. Algorithms and Performance Analysis, CRC Press, Boca Raton (2004)
Ford, L., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962)
Gale, D.: A theorem on flows in networks. Pacific J. Math. 7, 1073–1082 (1957)
Gomes, C., Regin, J.-C.: The alldiff matrix. Technical report, Intelligent Information Institute - Cornell University (2003)
Katricl, I., Thiel, S.: Fast bound consistency for the global cardinality constraint. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 437–451. Springer, Heidelberg (2003)
Kocjan, W., Kreuger, P.: Filtering methods for symmetric cardinality constraints. In: Régin, J.-C., Rueher, M. (eds.) CPAIOR 2004. LNCS, vol. 3011, pp. 200–208. Springer, Heidelberg (2004)
Milano, M. (ed.): Constraint and Integer Programming: Toward a Unified Methodology. Kluwer, Dordrecht (2003)
Regfn, J.-C.: Generalized arc consistency for global cardinality constraint. In: Proceedings AAAI 1996, Portland, Oregon, pp. 209–215 (1996)
Ryser, H.: A combinatorial theorem with application to latin rectangles. Proa. Amec. Math. Soc. 2, 550–552 (1951)
Ryser, H.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9, 371–377 (1957)
Tarjan, R.: Depth-first search and linear graph algorithms. SI AM Journal of Computing 1, 146–160 (1972)
Tarjan, R.: Data Structures and Network Algorithms. In: CBMS-XSF Regional Conference Series in Applied Mathematics (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Régin, JC., Gomes, C.P. (2004). The Cardinality Matrix Constraint . In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_42
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive