×

zbMATH — the first resource for mathematics

The complexity of reasoning with global constraints. (English) Zbl 1124.68103
Summary: Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Software:
cc(FD)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beldiceanu, N. (2000). Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type. Technical Report, Swedish Institute of Computer Science. SICS Technical Report T2000/01. · Zbl 1044.68737
[2] Beldiceanu, N. (2000). Global constraints as graph properties on a structured network of elementary constraints of the same type. In Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP’00), LNCS 1894, Singapore, pages 52–66. Berlin Heidelberg New York: Springer. · Zbl 1044.68737
[3] Beldiceanu, N. (2001). Pruning for the minimum constraint family and for the number of distinct values constraint family. In Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP’01), LNCS 2239, Singapore, pages 211–224. Berlin Heidelberg New York: Springer. · Zbl 1067.68611
[4] Beldiceanu, N., & Carlsson, M. (2001). Revisiting the cardinality operator and introducing cardinality-path constraint family. In Proceedings ICLP’01, pages 59–73. Berlin Heidelberg New York: Springer. · Zbl 1053.68521
[5] Beldiceanu, N., & Contegean, E. (1994). Introducing global constraints in CHIP. Math. Comput. Model. 20(12): 97–123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9
[6] Bessiere, C. (2005). Complexity of the cardpath Constraint. Technical Report TR-05036, LIRMM (CNRS/University of Montpellier), Montpellier, France, (January).
[7] Bessiere, C., Hebrard, E., Hnich, B., Kiziltan, Z., & Walsh, T. (2005). Filtering algorithms for the NValue constraint. In Proceedings CPAIOR’05, Prague, Czech Republic. · Zbl 1133.68427
[8] Bessiere, C., & Régin, J.C. (1997). Arc consistency for general constraint networks: preliminary results. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI’97), Nagoya, Japan, pages 398–404.
[9] Bessiere, C., & Van Hentenryck, P. (2003). To be or not to be ... a global constraint. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), LNCS 2833. Kinsale, Ireland, pages 789–794. Berlin Heidelberg New York: Springer (Short paper). · Zbl 1273.68334
[10] Carlsson, M., & Beldiceanu, N. (2002). Arc-consistency for a Chain of Lexicographic Ordering Constraints. Technical Report T2002-18, Swedish Institute of Computer Science, Sweden. ftp://ftp.sics.se/pub/SICS-reports/Reports/SICS-T-2002-18-SE.ps.Z .
[11] Caseau, Y., & Laburthe, F. (1997). Solving various weighted matching problems with constraints. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP’97), LNCS 1330. Linz, Austria, pages 17–31. Berlin Heidelberg New York: Springer. · Zbl 0949.90058
[12] Cohen, D. A., Jeavons, P., & Koubarakis, M. (1997). Tractable disjunctive constraints. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP’97), LNCS 1330. Linz, Austria, pages 478–490. Berlin Heidelberg New York: Springer. · Zbl 1320.68169
[13] Dechter, R., & Pearl, J. (1988). Network-based heuristics for constraint-satisfaction problems. Artif. Intell. 34: 1–38. · Zbl 0643.68156 · doi:10.1016/0004-3702(87)90002-6
[14] Dechter, R., & Pearl, J. (1989). Tree clustering for constraint networks. Artif. Intell. 38: 353–366. · Zbl 0665.68084 · doi:10.1016/0004-3702(89)90037-4
[15] Deville, Y., Barette, O., & Van Hentenryck, P. (1997). Constraint satisfaction over connected row convex constraints. In Proceedings IJCAI’97. Nagoya, Japan, pages 405–410. · Zbl 0916.68061
[16] Focacci, F., Lodi, A., & Milano, M. (2002). Optimization-oriented global constraints. Constraints 7: 351–365. · Zbl 1028.68024 · doi:10.1023/A:1020589922418
[17] Freuder, E. C. (1982). A sufficient condition for backtrack-free search. J. ACM 29(1): 24–32 (January). · Zbl 0477.68063 · doi:10.1145/322290.322292
[18] Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., & Walsh, T. (2002). Global constraints for lexicographic orderings. In Proceedings of the Eight International Conference on Principles and Practice of Constraint Programming (CP’02), LNCS 2470. Ithaca, NY, pages 93–108. Berlin Heidelberg New York: Springer.
[19] Garey, M. R. & Johnson, D. S. (1979). Computers and intractability: A guide to NP-completeness. San Francisco, California: Freeman. · Zbl 0411.68039
[20] Gottlob, G., Leone, N., & Scarcello, F. (1999). A comparison of structural CSP decomposition methods. In Proceedings IJCAI’99. Stockholm, Sweden, pages 394–399. · Zbl 0952.68044
[21] Hnich, B., Kiziltan, Z., & Walsh, T. (2004). Combining symmetry breaking with other constraints: lexicographic ordering with sums. In Proceedings of the 8th International Symposium on the Artificial Intelligence and Mathematics. Fort Lauderdale, Florida, USA.
[22] Knuth, D. E., & Raghunathan, A. (1992). The problem of compatible representatives. SIAM J. Discrete Math. 5(3): 422–427. · Zbl 0825.68494 · doi:10.1137/0405033
[23] Lhomme, O. (2004). Arc-consistency filtering algorithms for logical combinations of constraints. In Proceedings CPAIOR’04. Nice, France, pages 209–224. · Zbl 1094.68648
[24] Mohr, R., & Masini, G. (1988). Good old discrete relaxation. In Proceedings ECAI’88, Munchen, Germany, pages 651–656.
[25] Pachet, F., & Roy, P. (1999). Automatic generation of music programs. In Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP’99), LNCS 1713. Alexandria, Virginia, pages 331–345. Berlin Heidelberg New York: Springer.
[26] Papadimitriou, C. H., & Yannakakis, M. (1984). The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28: 244–259. · Zbl 0571.68028 · doi:10.1016/0022-0000(84)90068-0
[27] Quimper, C. (2003). Enforcing Domain Consistency on the Extended Global Cardinality Constraint is NP-hard. Technical Report CS-2003-39, School of Computer Science, University of Waterloo, Ontario, Canada.
[28] Régin, J.C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings AAAI’94. Seattle, Washington, pages 362–367. AAAI Press
[29] Régin, J.C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings AAAI’96. Portland, Oregon, pages 209–215. MIT.
[30] Régin, J. C. (2002). Cost-based arc consistency for global cardinality constraints. Constraints 7: 387–405. · Zbl 1028.68157 · doi:10.1023/A:1020506526052
[31] Régin, J. C., & Rueher, M. (2000). A global constraint combining a sum constraint and difference constraint. In Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP’00), LNCS 1894. Singapore, pages 384–395. Berlin Heidelberg New York: Springer. · Zbl 1044.68794
[32] Sadler, A., & Gervet, C. (2001). Global reasoning on sets. In Proceedings of Workshop on Modelling and Problem Formulation (FORMUL’01), held alongside CP-01. Paphos, Cyprus.
[33] Sellmann, M. (2003). Approximated consistency for knapsack constraints. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), LNCS 2833. Kinsale, Ireland, pages 679–693. Berlin Heidelberg New York: Springer. · Zbl 1273.90179
[34] Sellmann, M. (2003). Cost-based filtering for shorter path constraints. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), LNCS 2833. Kinsale, Ireland, pages 694–708. Berlin Heidelberg New York: Springer. · Zbl 1273.90231
[35] van Beek, P., & Dechter, R. (1995). On the minimality and global consistency of row-convex constraint networks. J. ACM 42(3): 543–561. · Zbl 0885.68087 · doi:10.1145/210346.210347
[36] Van Hentenryck, P., & Deville, Y. (1991). The cardinality operator: a new logical connective for constraint logic programming. In Proceedings ICLP’91. Paris, France, pages 745–759.
[37] Van Hentenryck, P., Saraswat, V., & Deville, Y. (1998). Design, implementation and evaluation of the constraint language cc(fd). J. Log. Program. 37(1–3): 139–164. · Zbl 0920.68026 · doi:10.1016/S0743-1066(98)10006-7
[38] Wallace, M. (1996). Practical applications of constraint programming. Constraints 1: 139–168 (September). · Zbl 05475105 · doi:10.1007/BF00143881
[39] Walsh, T. (2003). Consistency and propagation with multiset constraints: a formal viewpoint. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), LNCS 2833. Kinsale, Ireland, pages 724–738. Berlin Heidelberg New York: Springer. · Zbl 1273.68364
[40] Walsh, T. (2003). Constraint patterns. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), LNCS 2833, Kinsale, Ireland. Berlin Heidelberg New York: Springer.
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.