×

zbMATH — the first resource for mathematics

Global constraint catalogue: past, present and future. (English) Zbl 1128.68092
The article addresses the problem of global constraints focusing on their graph based description. In the first part the authors review the existing techniques in the literature related to the systematic graph property based filtering. The second part proposes a generic filtering scheme by combining existing and new techniques. Several possible enhancements as well as possible research directions are suggested. The approach used is based on reformulating a global constraint into a satisfaction problem according to its graph properties. A filtering algorithm is synthesised by searching for the relevant formula and components in a database of bounds and graph invariants.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggoun, A., & Beldiceanu, N. (1993). Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7), 57–73. · Zbl 00269355 · doi:10.1016/0895-7177(93)90068-A
[2] Baptiste, P., & Le Pape, C. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1/2), 119–139. · Zbl 0941.90030 · doi:10.1023/A:1009822502231
[3] Baptiste, P., & Demassey, S. (2004). Tight LP bounds for resource constrained project scheduling. OR-Spektrum, 26, 251–262. · Zbl 1072.90012
[4] Beldiceanu, N. (1990). An example of introduction of global constraints in CHIP: Application to block theory problems. Technical report TR-LP-49, ECRC, Munich.
[5] Beldiceanu, N. (2000). Global constraints as graph properties on a structured network of elementary constraints of the same type. In R. Dechter (Ed.), Principles and practice of Constraint Programming (CP’2000), volume 1894 of LNCS (pp. 52–66). Berlin Heidelberg New York: Springer. Preprint available as SICS Tech Report T2000-01. · Zbl 1044.68737
[6] Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 20(12), 97–123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9
[7] Beldiceanu, N., & Petit, T. (2004). Cost evaluation of soft global constraints. In J.-C. Régin & M. Rueher (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 3011 of LNCS (pp. 80–95). Berlin Heidelberg New York: Springer. · Zbl 1094.68638
[8] Beldiceanu, N., Carlsson, M., & Petit, T. (2004). Deriving filtering algorithms from constraint checkers. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp 107–122). Berlin Heidelberg New York: Springer. Preprint available as SICS Tech Report T2004-08. · Zbl 1152.68539
[9] Beldiceanu, N., Katriel, I., & Thiel, S. (2004). Filtering algorithms for the same constraint. In J.-C. Régin & M. Rueher (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR 2004), volume 3011 of LNCS (pp 65–79). Berlin Heidelberg New York: Springer. · Zbl 1094.68637
[10] Beldiceanu, N., Carlsson, M., Debruyne, R., & Petit, T. (2005). Reformulation of global constraints based on constraint checkers. Constraints, 10(3), 339–362. · Zbl 1103.68804 · doi:10.1007/s10601-005-2809-x
[11] Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global constraint catalog. Technical Report T2005-06, Swedish Institute of Computer Science, Kista.
[12] Beldiceanu, N., Carlsson, M., Rampon, J.-X., & Truchet, C. (2005). Graph invariants as necessary conditions for global constraints. In P. van Beek (Ed.), Principles and Practice of Constraint Programming (CP’2005), volume 3709 of LNCS (pp 92–106). Berlin Heidelberg New York: Springer. Preprint available as SICS Tech Report T2005-07. · Zbl 1153.68446
[13] Beldiceanu, N., Flener, P., & Lorca, X. (May 2005) The tree constraint. In R. Barták & M. Milano (Eds.), International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’05), volume 3524 of LNCS (pp. 64–78). Prague, Czech Republic. Berlin Heidelberg New York: Springer. · Zbl 1133.90403
[14] Beldiceanu, N., Katriel, I., & Thiel, S. (2005). GCC-like restrictions on the same constraint. In B. Faltings, A. Petcu, F. Fages, & F. Rossi (Eds.), Springer LNAI volume based on the 2004 edition of the ERCIM/Colognet workshop on Constraint Solving and Constraint Logic Programming (CSCLP04), volume 3419 of LNAI (pp. 1–11). Berlin Heidelberg New York: Springer. · Zbl 1078.68744
[15] Beldiceanu, N., Petit, T., & Rochart, G. (2005). Bounds of graph characteristics. In P. van Beek (Ed.), Principles and Practice of Constraint Programming (CP’2005), volume 3709 of LNCS (pp. 742–746). Berlin Heidelberg New York: Springer. · Zbl 1153.68447
[16] Beldiceanu, N., Petit, T., & Rochart, G. (2005). Bounds of graph characteristics. Technical Report 05/2/INFO. Ecole des Mines, Paris. · Zbl 1153.68447
[17] Beldiceanu, N., Carlsson, M., Demassey, S., & Petit, T. (2006). Graph properties based filtering. Technical Report T2006-10, Swedish Institute of Computer Science, Kista, Sweden.
[18] Beldiceanu, N., Katriel, I., & Lorca, X. (2006). Undirected forest constraints. In CP-AI-OR’06, volume 3990 of LNCS. Berlin Heidelberg New York: Springer. · Zbl 1177.90392
[19] Berge, C. (1970). Graphes. Dunod (in French). · Zbl 0213.25702
[20] Bessière, C., & Van Hentenryck, P. (2003). To be or not to be... a global constraint. In F. Rossi (Ed.), Principles and Practice of Constraint Programming (CP’2003), volume 2833 of LNCS (pp. 789–794). Berlin Heidelberg New York: Springer. · Zbl 1273.68334
[21] Bessière, C., Coletta, R., & Petit, T. (2005). Acquiring parameters of implied global constraints. In P. van Beek (Ed.), Principles and Practice of Constraint Programming (CP’2005), volume 3709 of LNCS (pp. 747–751). Berlin Heidelberg New York: Springer. · Zbl 1153.68449
[22] Bessière, C., Hebrard, E., Hnich, B., Kızıltan, Z., & Walsh, T. (2005). Among, common and disjoint constraints. In CSCLP 2005, pp. 223–235. Uppsala, Sweden. Berlin Heidelberg New York: Springer.
[23] Bessière, C., Hebrard, E., Hnich, B., Kızıltan, Z., & Walsh, T. (May 2005). Filtering algorithms for the nvalue constraint. In R. Barták & M. Milano (Eds.), International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’05), volume 3524 of LNCS, (pp. 79–93). Prague, Czech Republic. Berlin Heidelberg New York: Springer. · Zbl 1133.68427
[24] Bleuzen-Guernalec, N., & Colmerauer, A. (1997). Narrowing a block of sortings in quadratic time. In G. Smolka (Ed.), Principles and Practice of Constraint Programming (CP’97), volume 1330 of LNCS (pp. 2–16). Berlin Heidelberg New York: Springer. · Zbl 0947.68045
[25] Card, S. K., Mackinlay, J. D., & Shneiderman, B. (1999). Readings in information visualization using vision to think. Morgan Kaufmann.
[26] Carlsson, M., & Beldiceanu, N. (2002). Arc-consistency for a chain of lexicographic ordering constraints. Technical Report T2002-18, Swedish Institute of Computer Science, Kista, Sweden.
[27] Caseau, Y., & Laburthe, F. (1996). Cumulative scheduling with task intervals. In Joint International Conference and Symposium on Logic Programming (JICSLP’96). MIT Press.
[28] Colton, S., & Miguel, I. (2001). Constraint generation via automated theory formation. In T. Walsh (Ed.), Principles and Practice of Constraint Programming (CP’2001), volume 2239 of LNCS (pp. 575–579). Berlin Heidelberg New York: Springer. · Zbl 1067.68622
[29] Costa, M.-C. (1994). Persistency in maximum cardinality bipartite matchings. Operation Research Letters, 15, 143–149. · Zbl 0810.90126 · doi:10.1016/0167-6377(94)90049-3
[30] Deransart, P., Hermenegildo, M. V., & Maluszynski, J. (Eds.) (2000). Analysis and Visualization Tools for Constraint Programming, Constraint Debugging (DiSCiPl project), volume 1870 of LNCS. Berlin Heidelberg New York: Springer.
[31] Dincbas, M., Van Hentenryck, P., Simonis, H., Graf, T., Aggoun, A., & Berthier, F. (1988). The constraint logic programming language CHIP. In International Conference on Fifth Generation Computer Systems (FGCS’88) (pp. 693–702). Tokyo, Japan: ICOT.
[32] Dooms, G., Deville, Y., & Dupont, P. (2005). CP(Graph): Introducing a graph computation domain in constraint. In P. van Beek (Ed.), Principles and Practice of Constraint Programming (CP’2005), volume 3709 of LNCS (pp. 211–225). Berlin Heidelberg New York: Springer. · Zbl 1153.68457
[33] Dudeney, H. E. (1919). The Canterbury puzzles. Nelson.
[34] Elbassioni, K. M., Katriel, I., Kutz, M., & Mahajan, M. (2005). Simultaneous matchings. In Algorithms and Computation, 16th International Symposium (ISAAC 2005), volume 3827 of LNCS (pp. 106–115). Berlin Heidelberg New York: Springer. · Zbl 1144.68336
[35] Erschler, J., & Lopez, P. (June 1990). Energy-based approach for task scheduling under time and resources constraints. In 2nd International Workshop on Project Management and Scheduling (pp. 115–121). France: Compiégne.
[36] Euler, L. (1759). Solution d’une question curieuse qui ne parait soumise à aucune analyse. Mm. Acad. Sci. Berlin, 15, 310–337.
[37] Flener, P., Frisch, A. M., Hnich, B., Kızıltan, Z., Miguel, I., & Walsh, T. (2002). Matrix modelling: Exploiting common patterns in constraint programming. In A. M. Frisch (Ed.), Proceedings of the International Workshop on Reformulating CSPs, held at CP’02.
[38] Freuder, E. C. (1997). In pursuit of the holy grail. Constraints, 2(1), 57–61. · Zbl 05469273 · doi:10.1023/A:1009749006768
[39] Frisch, A. M., Jefferson, C., Martinez-Hernandez, B., & Miguel, I. (2005). The rules of constraint modelling. In 19th International Joint Conference on Artificial Intelligence (IJCAI-05) (pp. 109–116).
[40] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. A guide to the theory of NP-completeness. Freeman. · Zbl 0411.68039
[41] Guéret, C., Jussien, N., Boizumault, P., & Prins, C. (August 1995). Building university timetables using constraint logic programming. In ICPTAT’95: First International Conference on the Practice and Theory of Automated Time Tabling (pp. 393–408). Edinburgh, United Kingdom.
[42] Hansen, P. (2005). How far is, should and could be conjecture-making in graph theory an automated process? In S. Fajtlowicz, P. W. Fowler, P. Hansen, M. F. Janowitz, & F. S. Roberts (Eds.), Graphs and Discovery, volume 69 of DIMACS: Series in discrete mathematics and theoretical computer science (pp. 189–230). American Mathematical Society, DIMACS. · Zbl 1097.68588
[43] Henriksen, J. G., Jensen, J. L., Jørgensen, M. E., Klarlund, N., Paige, R., Rauhe, T., & Sandholm, A. (May 1995). Mona: Monadic second-order logic in practice. In E. Brinksma, R. Cleaveland, K. G. Larsen, T. Margaria, & B. Steffen (Eds.), Tools and Algorithms for Construction and Analysis of Systems, First International Workshop, TACAS’95, Aarhus, Denmark, volume 1019 of LNCS (pp. 89–110). Berlin Heidelberg New York: Springer.
[44] Hnich, B. (January 2003). Function variables for constraint programming. Ph.D. Thesis, Department of Information Science, Uppsala University. · Zbl 1159.68390
[45] Hooker, J. (October 2005). Past and future of CP. Panel, ”The Past and Future of Constraint Programming” at the Eleventh International Conference on Principles and Practice of Constraint Programming. Available at http://www.iiia.csic.es/cp2005/CP05-panel-hooker.pdf .
[46] Hooker, J. N., & Yan, H. (2002). A relaxation for the cumulative constraint. In P. Van Hentenryck (Ed.), Principles and Practice of Constraint Programming (CP’2002), volume 2470 of LNCS (pp. 686–690). Berlin Heidelberg New York: Springer.
[47] Katriel, I., & Thiel, S. (2003). Fast bound consistency for the global cardinality constraint. In F. Rossi (Ed.), Principles and Practice of Constraint Programming (CP’2003), volume 2833 of LNCS (pp. 437–451). Berlin Heidelberg New York: Springer. · Zbl 1273.68400
[48] Katriel, I., & Thiel, S. (2005). Complete bound consistency for the global cardinality constraint. Constraints, 10(3), 191–217. · Zbl 1084.68138 · doi:10.1007/s10601-005-2237-y
[49] Kirkman, T. P. (1847). On a problem in combinatorics. Cambridge and Dublin Math. J., 2, 191–204.
[50] Lahrichi, A. (February 1982). Scheduling: The notions of hump, compulsory parts and their use in cumulative poblems. C.R. Acad. Sci., Paris 294: 209–211. · Zbl 0496.68023
[51] Laurière, J.-L. (1996). Constraint propagation or automatic programming? Technical Report Laforia, number 19, Institut Blaise Pascal (in French).
[52] Leconte, M. (1996). A bounds-based reduction scheme for constraints of difference. In CP’96, Second International Workshop on Constraint-based Reasoning (pp. 19–28). Key West, FL.
[53] Lopez-Ortiz, A., Quimper, C.-G., Tromp, J., & van Beek, P. (2003). A fast and simple algorithm for bounds consistency of the alldifferent constraint. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’2003) (pp. 245–250).
[54] Lucas, E. (1882). Récréations Mathématiques, volume 1-2. Gauthier-Villars.
[55] Mehlhorn, K. (2000). Constraint programming and graph algorithms. In U. Montanari, J. D. P. Rolim, & E. Welzl (Eds.), 27th International Colloquium on Automata, Languages and Programming (ICALP’2000), volume 1853 of LNCS (pp. 571–575). Berlin Heidelberg New York: Springer. · Zbl 0973.68252
[56] Mehlhorn, K., & Thiel, S. (2000). Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint. In Principles and Practice of Constraint Programming (CP’2000), volume 1894 of LNCS (pp. 306–319). Berlin Heidelberg New York: Springer. · Zbl 1044.68783
[57] Milano, M., Ottoson, G., Refalo, P., & Thorsteinsson, E. (2002). The role of integer programming techniques in constraint programming’s global constraints. INFORMS Journal on Computing, 14(4), 387–402. · Zbl 1238.90101 · doi:10.1287/ijoc.14.4.387.2830
[58] Pachet, F., & Roy, P. (1999). Automatic generation of music programs. In Principles and Practice of Constraint Programming (CP’99), volume 1713 of LNCS (pp. 331–345). Berlin Heidelberg New York: Springer.
[59] Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp. 482–495). Berlin Heidelberg New York: Springer. · Zbl 1152.68573
[60] Petit, T., Régin, J.-C., & Bessière, C. (2001). Specific filtering algorithms for over-constrained problems. In T. Walsh (Ed.), Principles and Practice of Constraint Programming (CP’2001), volume 2239 of LNCS (pp. 451–463). Berlin Heidelberg New York: Springer. · Zbl 1067.68663
[61] Pitrat, J. (September 2001). MALICE, notre collègue. In Colloque Métaconnaissance de Berder (pp. 4–19). In French.
[62] Puget, J.-F. (November 1994). A C++ implementation of CLP. In Second Singapore International Conference on Intelligent Systems (SPICIS), pp. 256–261. Singapore.
[63] Puget, J.-F. (1998). A fast algorithm for the bound consistency of alldiff constraints. In 15th National Conference on Artificial Intelligence (AAAI-98) (pp. 359–366). AAAI Press.
[64] Puget, J.-F. (2004). Constraint programming next challenge: Simplicity of use. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp. 5–8). Berlin Heidelberg New York: Springer.
[65] Puget, J.-F. (2005). Automatic detection of variable and value symmetries. In P. van Beek (Ed.), Principles and Practice of Constraint Programming (CP’2005), volume 3709 of LNCS (pp. 475–489). Berlin Heidelberg New York: Springer. · Zbl 1153.68477
[66] Quimper, C.-G., van Beek, P., López-Ortiz, A., Golynski, A., & Sadjad, S. B. (2003). An efficient bounds consistency algorithm for the global cardinality constraint. In F. Rossi (Ed.), Principles and Practice of Constraint Programming (CP’2003), volume 2833 of LNCS (pp. 600–614). Berlin Heidelberg New York: Springer. · Zbl 1273.68361
[67] Quimper, C.-G., López-Ortiz, A., van Beek, P., & Golynski, A. (2004). Improved algorithms for the global cardinality constraint. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp. 542–556). Berlin Heidelberg New York: Springer. · Zbl 1152.68576
[68] Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSP. In 12th National Conference on Artificial Intelligence (AAAI-94), pp. 362–367.
[69] Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In 14th National Conference on Artificial Intelligence (AAAI-96), pp. 209–215.
[70] Régin, J.-C. (1999). The symmetric alldiff constraint. In 16th International Joint Conference on Artificial Intelligence (IJCAI-99), pp. 420–425.
[71] Régin, J.-C., & Gomes, C. (2004). The cardinality matrix constraint. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp. 572–587). Berlin Heidelberg New York: Springer. · Zbl 1152.68578
[72] Régin, J.-C., & Rueher, M. (1999). A global constraint combining a sum constraint and binary inequalities. In IJCAI-99 Workshop on Non Binary Constraints.
[73] Rochart, G., & Jussien, N. (2003). Explanations for Global Constraints: Instrumenting the Stretch Constraint. Technical report 03-01-INFO, École des Mines de Nantes.
[74] Simonis, H., Aggoun, A., Beldiceanu, N., & Bourreau, E. (2000). Complex constraint abstraction: Global constraint visualization. In P. Deransart, M. V. Hermenegildo, & J. Małuszyński (Eds.), Analysis and Vizualisation Tools for Constraint Programming, volume 1870 of LNCS (pp. 299–317). Berlin Heidelberg New York: Springer.
[75] Turán, P. (1941). On an extremal problem in graph theory. Matematikai es’ Fizikai Lapok, 48, 436–452. In Hungarian.
[76] Van Hentenryck, P. (1997). Constraint programming for combinatorial search problems. Constraints, 2(1), 99–101. · Zbl 1315.68070 · doi:10.1023/A:1009713426332
[77] Van Hentenryck, P. (1999). The OPL optimization programming language. MIT Press.
[78] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. MIT Press. · Zbl 1153.90582
[79] van Hoeve, W.-J. (2004). A hyper-arc consistency algorithm for the soft alldifferent constraint. In M. Wallace (Ed.), Principles and Practice of Constraint Programming (CP’2004), volume 3258 of LNCS (pp. 679–689). Berlin Heidelberg New York: Springer. · Zbl 1152.68595
[80] van Hoeve, W.-J., Pesant, G., & Rousseau, L.-M. (September 2004). On global warming (softening global constraints). In Workshop on soft constraints. Toronto, Canada.
[81] Voigt, K. (1988). Incorporating global constraints. Technical Report LCSR-TR-114, Laboratory for Computer Science Research, Hill Center for the Mathematical Sciences, Busch Campus, Rutgers University, New Brunswick, NJ.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.