Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-27T14:45:56.690Z Has data issue: false hasContentIssue false
  • English
  • Français

Contractibility for open global constraints

Published online by Cambridge University Press:  27 June 2017

MICHAEL J. MAHER
MICHAEL J. MAHER*
Affiliation:
Reasoning Research Institute, Canberra, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems, where problem construction and problem solving are interleaved, and fit naturally within constraint logic programming. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints, where filtering remains sound when the constraint is open. With this characterization, we can easily determine whether a constraint has this property or not. In the latter case, we can use it to derive a contractible approximation to the constraint. We demonstrate this work on both hard and soft constraints. In the process, we formulate two general classes of soft constraints.

Keywords

global constraintsopen constraintssoft constraints
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 17 , Issue 4 , July 2017 , pp. 365 - 407
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barták, R. 1999. Dynamic constraint models for planning and scheduling problems. In New Trends in Constraints, Joint ERCIM/Compulog Net Workshop, Paphos, Cyprus, October 25–27, 1999.Google Scholar
Barták, R. 2003. Dynamic global constraints in backtracking based environments. Annals of Operations Research 118, 1–4, 101–119.CrossRefGoogle Scholar
Beldiceanu, N. and Carlsson, M. 2001. Revisiting the cardinality operator and introducing the cardinality-path constraint family. In Proc. of 17th International Conference on Logic Programming, ICLP, Paphos, Cyprus, November 26–December 1, 2001, 59–73.Google Scholar
Beldiceanu, N., Carlsson, M. and Rampon, J.-X. 2005. Global constraint catalog. Technical Report T2005:08, SICS. Current version available at http://sofdem.github.io/gccat/.Google Scholar
Beldiceanu, N. and Contejean, E. 1994. Introducing global constraints in CHIP. Mathematical Computer Modelling 20, 12, 97–123.CrossRefGoogle Scholar
Beldiceanu, N. and Petit, T. 2004. Cost evaluation of soft global constraints. In Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 1st International Conference, CPAIOR 2004, Nice, France, April 20–22, 2004, 80–95.Google Scholar
Bessière, C. 1991. Arc-consistency in dynamic constraint satisfaction problems. In Proc. of the 9th National Conference on Artificial Intelligence, Anaheim, CA, USA, July 14–19, 1991, vol. 1, 221–226.Google Scholar
Bessiere, C., Brito, I., Gutierrez, P. and Meseguer, P. 2014. Global constraints in distributed constraint satisfaction and optimization. Computer Journal 57, 6, 906–923.Google Scholar
Bessiere, C., Hebrard, E., Hnich, B., Kiziltan, Z. and Walsh, T. 2008. SLIDE: A useful special case of the CARDPATH constraint. In Proc. of 18th European Conference on Artificial Intelligence, ECAI, Patras, Greece, July 21–25, 2008, 475–479.Google Scholar
Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C. and Walsh, T. 2009. Decompositions of all different, global cardinality and related constraints. In Proc. of the 21st International Joint Conference on Artificial Intelligence, IJCAI, Pasadena, California, USA, July 11–17, 2009, 419–424.Google Scholar
Bistarelli, S., Montanari, U. and Rossi, F. 1997. Semiring-based constraint satisfaction and optimization. Journal of the ACM 44, 2, 201–236.CrossRefGoogle Scholar
Borning, A., Freeman-Benson, B. N. and Wilson, M. 1992. Constraint hierarchies. Lisp and Symbolic Computation 5, 3, 223–270.Google Scholar
Borning, A., Maher, M. J., Martindale, A. and Wilson, M. 1989. Constraint hierarchies and logic programming. In Proc. of 6th International Conference on Logic Programming, Lisbon, Portugal, June 19–23, 1989, 149–164.Google Scholar
Brzozowski, J. A., Shallit, J. and Xu, Z. 2009. Decision problems for convex languages. In Proc. of Language and Automata Theory and Applications, 3rd International Conference, LATA, 2009, Tarragona, Spain, April 2–8, 2009, 247–258.Google Scholar
Chandra, A. K. and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proc. of the 9th Annual ACM Symposium on Theory of Computing, May 4–6, 1977, Boulder, Colorado, USA, 77–90.Google Scholar
Chatterjee, K., Doyen, L. and Henzinger, T. A. 2010. Quantitative languages. ACM Transactions on Computational Logic 11, 4.CrossRefGoogle Scholar
Chaudhuri, S. and Vardi, M. Y. 1993. Optimization of Real conjunctive queries. In Proc. of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25–28, 1993, Washington, DC, USA, 59–70.Google Scholar
Colcombet, T. 2009. The theory of stabilisation monoids and regular cost functions. In Proc. of Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP Part II, Rhodes, Greece, July 5–12, 2009, 139–150.Google Scholar
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press and McGraw-Hill Book Company.Google Scholar
Debruyne, R., Ferrand, G., Jussien, N., Lesaint, W., Ouis, S. and Tessier, A. 2003. Correctness of constraint retraction algorithms. In Proc. of the 16th International Florida Artificial Intelligence Research Society Conference, May 12–14, 2003, St. Augustine, Florida, USA, 172–176.Google Scholar
Dechter, R. 2003. Constraint Processing. Elsevier Morgan Kaufmann.Google Scholar
Dechter, R. and Dechter, A. 1988. Belief maintenance in dynamic constraint networks. In Proc. of the 7th National Conference on Artificial Intelligence, St. Paul, MN, August 21–26, 1988, 37–42.Google Scholar
Faltings, B. and Macho-Gonzalez, S. 2002. Open constraint satisfaction. In Proc. of Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, 356–370.Google Scholar
Faltings, B. and Macho-Gonzalez, S. 2005. Open constraint programming. Artificial Intelligence 161, 1–2, 181–208.CrossRefGoogle Scholar
Frisch, A. M., Hnich, B., Kiziltan, Z., Miguel, I. and Walsh, T. 2002. Global constraints for lexicographic orderings. In Proc. of Principles and Practice of Constraint Programming – CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9–13, 93–108.Google Scholar
Gavanelli, M., Lamma, E., Mello, P. and Milano, M. 2005. Dealing with incomplete knowledge on clp(FD) variable domains. ACM Transactions on Programming Languages and Systems 27, 2, 236–263.CrossRefGoogle Scholar
Georget, Y., Codognet, P. and Rossi, F. 1999. Constraint retraction in CLP(FD): Formal framework and performance results. Constraints 4, 1, 5–42.Google Scholar
Gervet, C. 1997. Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints 1, 3, 191–244.Google Scholar
He, J., Flener, P. and Pearson, J. 2013. Underestimating the cost of a soft constraint is dangerous: Revisiting the edit-distance based soft regular constraint. Journal of Heuristics 19, 5, 729–756.Google Scholar
Hentenryck, P. V. and Provost, T. L. 1991. Incremental search in constraint logic programming. New Generation Computing 9, 3/4, 257–276.CrossRefGoogle Scholar
Hopcroft, J. and Ullman, J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley.Google Scholar
Ioannidis, Y. E. and Ramakrishnan, R. 1995. Containment of conjunctive queries: Beyond relations as sets. ACM Transaction on Database System 20, 3, 288–324.Google Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Klug, A. C. 1988. On conjunctive queries containing inequalities. Journal of ACM 35, 1, 146–160.Google Scholar
Lallouet, A., Law, Y. C., Lee, J. H. and Siu, C. F. K. 2011. Constraint programming on infinite data streams. In Proc. of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, Barcelona, Catalonia, Spain, July 16–22, 2011, 597–604.Google Scholar
Law, Y. C. and Lee, J. H. 2004. Global constraints for integer and set value precedence. In Proc. of Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27–October 1, 2004, 362–376.Google Scholar
Maher, M. J. 1988. Equivalences of logic programs. In Foundations of Deductive Databases and Logic Programming. Minker, J. (Ed). Morgan Kaufmann, 627–658.Google Scholar
Maher, M. J. 1993. A logic programming view of CLP. In Proc. of 10th International Conference on Logic Programming, Budapest, Hungary, June 21–25, 1993, 737–753.Google Scholar
Maher, M. J. 2002. Analysis of a global contiguity constraint. In Proc. of Workshop on Rule-Based Constraint Reasoning and Programming.Google Scholar
Maher, M. J. 2009a. Local consistency for extended CSPs. Theoretical Computer Science 410, 46, 4769–4783.Google Scholar
Maher, M. J. 2009b. Open constraints in a boundable world. In Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27–31, 2009, 163–177.Google Scholar
Maher, M. J. 2009c. Open contractible global constraints. In Proc. of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, 578–583.Google Scholar
Maher, M. J. 2009d. SOGgy constraints: Soft open global constraints. In Proc. of Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, September 20–24, 2009, 584–591.Google Scholar
Maher, M. J. 2010. Contractibility and contractible approximations of soft global constraints. In Proc. of Technical Communications of the 26th International Conference on Logic Programming, ICLP 2010, July 16–19, 2010, Edinburgh, Scotland, UK, 114–123.Google Scholar
Maher, M. J., Narodytska, N., Quimper, C. and Walsh, T. 2008. Flow-based propagators for the SEQUENCE and related global constraints. In Proc. of Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Sydney, Australia, September 14–18, 2008, 159–174.Google Scholar
Maher, M. J. and Stuckey, P. J. 1989. Expanding query power in constraint logic programming languages. In Proc. of the North American Conference 1989, Cleveland, Ohio, USA, October 16–20, 1989, vol. 2, 20–36.Google Scholar
Métivier, J., Boizumault, P. and Loudni, S. 2007. All different: Softening alldifferent in weighted CSPs. In Proc. of 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007), October 29–31, 2007, Patras, Greece, vol. 1, 223– 230.Google Scholar
Métivier, J., Boizumault, P. and Loudni, S. 2009. Softening GCC and regular with preferences. In Proc. of the 2009 ACM Symposium on Applied Computing (SAC), Honolulu, Hawaii, USA, March 9–12, 2009, 1392–1396.Google Scholar
Mittal, S. and Falkenhainer, B. 1990. Dynamic constraint satisfaction problems. In Proc. of the 8th National Conference on Artificial Intelligence, Boston, Massachusetts, July 29–August 3, 1990, vol. 2, 25–32.Google Scholar
Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J. and Tack, G. 2007. Minizinc: Towards a standard CP modelling language. In Proc. of Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23–27, 2007, 529–543.Google Scholar
Pachet, F. and Roy, P. 1999. Automatic generation of music programs. In Proc. of Principles and Practice of Constraint Programming - CP'99, 5th International Conference, Alexandria, Virginia, USA, October 11–14, 1999, 331–345.Google Scholar
Pesant, G. 2004. A regular language membership constraint for finite sequences of variables. In Proc. of Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 1, 2004, 482–495.Google Scholar
Petit, T. and Poder, E. 2009. The soft cumulative constraint. CoRR abs/0907.0939.Google Scholar
Petit, T., Régin, J. and Bessière, C. 2001. Specific filtering algorithms for over-constrained problems. In Proc. of Principles and Practice of Constraint Programming - CP 2001, 7th International Conference, CP 2001, Paphos, Cyprus, November 26–December 1, 2001, 451–463.Google Scholar
Quimper, C. and Walsh, T. 2006. Global grammar constraints. In Proc. of Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25–29, 2006, 751–755.Google Scholar
Régin, J. 1994. A filtering algorithm for constraints of difference in CSPs. In Proc. of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31–August 4, 1994, vol. 1, 362–367.Google Scholar
Régin, J. 1996. Generalized arc consistency for global cardinality constraint. In Proc. of the 13th National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI 96, Portland, Oregon, August 4–8, 1996, vol. 1, 209–215.Google Scholar
Rossi, F., van Beek, P. and Walsh, T., Eds. 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence, vol. 2. Elsevier.Google Scholar
Schiex, T., Fargier, H. and Verfaillie, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In Proc. of the 14th International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20–25 1995, vol. 2, 631–639.Google Scholar
Schulte, C. and Tack, G. 2009. Weakly monotonic propagators. In Proc. of Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, September 20–24, 2009, 723–730.Google Scholar
Sellmann, M. 2006. The theory of grammar constraints. In Proc. of Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, 530–544.Google Scholar
van Hoeve, W. J., Pesant, G. and Rousseau, L. 2006. On global warming: Flow-based soft global constraints. Journal of Heuristics 12, 4-5, 347–373.Google Scholar
van Hoeve, W. J. and Régin, J. 2006. Open constraints in a closed world. In Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 3rd International Conference, CPAIOR 2006, Cork, Ireland, May 31–June 2, 2006, 244–257.Google Scholar
Verfaillie, G. and Jussien, N. 2005. Constraint solving in uncertain and dynamic environments: A survey. Constraints 10, 3, 253–281.CrossRefGoogle Scholar