When do bounds and domain propagation lead to the same search space?

ABSTRACT

This article explores the question of when two propagation-based constraint systems have the same behavior, in terms of search space. We categorize the behavior of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviors for conjunctions of constraints. We then show how we can use this to analyze CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space. Empirical evaluation shows that programs optimized by the analysis' results are considerably more efficient.

REFERENCES

• 1: Apt, K. 2003. Principles of Constraint Programming. Cambridge University Press, Cambridge, U.K.
• 2: Philippe Baptiste , Claude Le Pape , Wim Nuijten, Constraint-Based Scheduling, Kluwer Academic Publishers, Norwell, MA, 2001
• 3: Beasley, J. E. 1990. OR library: Distributing test problems by electronic mail. J. Open. Res. Soc. 41, 11 (Nov.), 1069--1072. (URL: http://www.ms.ic.ac.uk/info.html).
• 4: Demoen, B., García de la Banda, M., and Stuckey, P. J. 1999. Type constraint solving for parametric and ad-hoc polymorphism. In Proceedings of the 22nd Australasian Computer Science Conference (Auckland, New Zealand), J. Edwards, Ed. Springer-Verlag, New York, NY, 217--228.
• 5: Mehmet Dincbas , Helmut Simonis , Pascal Van Hentenryck, Solving large combinatorial problems in logic programming, Journal of Logic Programming, v.8 n.1-2, p.75-93, Jan./Mar. 1990 [doi>10.1016/0743-1066(90)90052-7]
• 6: M. Garcia de la Banda , M. Hermenegildo , M. Bruynooghe , V. Dumortier , G. Janssens , W. Simoens, Global analysis of constraint logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.564-614, Sept. 1996 [doi>10.1145/232706.232734]
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: Harvey, W. and Schimpf, J. 2002. Bounds consistency techniques for long linear constraints. In Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a workshop of CP 2002, N. Beldiceanu, P. Brisset, M. Carlsson, F. Laburthe, M. Henz, E. Monfroy, L. Perron, and C. Schulte, Eds. Number TRA9/02. 55 Science Drive 2, Singapore 117599, 39--46.
• 9: Warwick Harvey , Peter J. Stuckey, Improving Linear Constraint Propagation by Changing Constraint Representation, Constraints, v.8 n.2, p.173-207, April 2003 [doi>10.1023/A:1022323717928]
• 10: Andrew D. Kelly , Kim Marriott , Andrew MacDonald , Peter J. Stuckey , Roland Yap, Optimizing compilation of CLP( R ), ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1223-1250, Nov. 1998 [doi>10.1145/295656.295661]
• 11: Vitaly Lagoon , Peter J. Stuckey, A Framework for Analysis of Typed Logic Programs, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.296-310, March 07-09, 2001
• 12: David Lesaint, Inferring Constraint Types in Constraint Programming, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.492-507, September 09-13, 2002
• 13: Marriott, K. and Stuckey, P. J. 1998. Programming with Constraints: An Introduction. MIT Press, Cambridge, MA.
• 14: Kim Marriott , Harald Søndergaard, Analysis of constraint logic programs, Proceedings of the 1990 North American conference on Logic programming, p.531-547, January 1990, Austin, Texas, United States
• 15: Paul Martin , David B. Shmoys, A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.389-403, June 03-05, 1996
• 16: Kurt Mehlhorn , Sven Thiel, Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.306-319, September 18-21, 2000
• 17: Mozart Consortium. 1999. The Mozart programming system. Available online from www.mozart-oz.org.
• 18: Jean-Francois Puget, A fast algorithm for the bound consistency of alldiff constraints, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.359-366, July 1998, Madison, Wisconsin, United States
• 19: Quimper, C.-G., van Beek, P., López-Ortiz, A., Golynski, A., and Sadjad, S. B. 2003. An efficient bounds consistency algorithm for the global cardinality constraint. In Principles and Practice of Constraint Programming---CP 2003 (Kinsale, Ireland), F. Rossi, Ed. Lecture Notes in Computer Science, vol. 2833. Springer-Verlag, New York, NY, 600--614.
• 20: Jean-Charles Régin , Michel Rueher, A Global Constraint Combining a Sum Constraint and Difference Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.384-395, September 18-21, 2000
• 21: Jean-Charles Régin, A filtering algorithm for constraints of difference in CSPs, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.362-367, October 1994, Seattle, Washington, United States
• 22: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 23: Pascal Van Hentenryck, The OPL optimization programming language, MIT Press, Cambridge, MA, 1999
• 24: Van Hentenryck, P., Saraswat, V., and Deville, Y. 1998. Design, implementation and evaluation of the constraint language cc(FD). J. Logic Prog. 37, 1--3, 139--164.
• 25: Yuanlin Zhang , Roland H. C. Yap, Arc Consistency on n-ary Monotonic and Linear Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.470-483, September 18-21, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Constraints

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Experimentation, Languages, Performance, Theory

Keywords:
Constraint (logic) programming, abstract interpretation, bounds propagation, domain propagation, finite domain constraints, program analysis