Efficient constraint propagation engines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient constraint propagation engines

Full text

Pdf (310 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 31 , Issue 1 (December 2008) table of contents

Article No. 2

Year of Publication: 2008

ISSN:0164-0925

Authors

Christian Schulte	KTH - Royal Institute of Technology, Kista, Sweden
Peter J. Stuckey	NICTA Victoria Laboratory, University of Melbourne, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 227, Citation Count: 1

Additional Information:

abstract references cited by additional resources index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1452044.1452046 What is a DOI?

ABSTRACT

This article presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine several propagators for the same constraint.

We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current variable domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators that combine the effects of multiple propagators with priorities for greater efficiency.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Krzysztof Apt, Principles of Constraint Programming, Cambridge University Press, New York, NY, 2003
	2	Philippe Baptiste , Claude Le Pape , Wim Nuijten, Constraint-Based Scheduling, Kluwer Academic Publishers, Norwell, MA, 2001
	3	Beldiceanu, N., Harvey, W., Henz, M., Laburthe, F., Monfroy, E., Müller, T., Perron, L., and Schulte, C. 2000. In Proceedings of Techniques for Implementing Constraint Programming Systems (TRICS). Tech. rep. TRA9/00, School of Computing, National University of Singapore.
	4	Frédéric Benhamou, Heterogeneous Constraint Solving, Proceedings of the 5th International Conference on Algebraic and Logic Programming, p.62-76, September 25-27, 1996
	5	Carlsson, M. and Beldiceanu, N. 2002. Revisiting the lexicographic ordering constraint. Tech. rep. T2002-17, Swedish Institute of Computer Science, Stockholm, Sweden.
	6	Mats Carlsson , Greger Ottosson , Björn Carlson, An Open-Ended Finite Domain Constraint Solver, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.191-206, September 03-05, 1997
	7	Chamard, A., Fischler, A., Guinaudeau, D.-B., and Guillard, A. 1995. CHIC lessons on CLP methodology. Tech. rep., Dassault Aviation.
	8	Choi, C. W., Harvey, W., Lee, J. H.-M., and Stuckey, P. J. 2006. Finite domain bounds consistency revisited. In Proceedings of Advances in Artificial Intelligence (AI2006). Lecture Notes in Computer Science, vol. 4304. Springer-Verlag, 49--58.
	9	Codognet, P. and Diaz, D. 1996. Compiling constraints in clp(FD). J. Logic Program. 27, 3, 185--226.
	10	CSPLib. 2006. CSPLib: A problem library for constraints. http://www.csplib.org.
	11	Dudeney, H. E. 1958. Amusements in Mathematics. Dover, New York.
	12	Gecode Team. 2006. Gecode: Generic constraint development environment. http://www.gecode.org.
	13	Gent, I. P., Jefferson, C., and Miguel, I. 2006. Watched literals for constraint propagation in Minion. In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming, F. Benhamou, Ed. Lecture Notes in Computer Science, vol. 4204. Springer-Verlag, 182--197.
	14	Granvilliers, L. and Monfroy, E. 2003. Implementing constraint propagation by composition of reductions. In Proceedings of the 19th International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 2916. Springer-Verlag, 300--314.
	15	Harvey, W. 2004. Personal communication.
	16	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]
	17	ILOG S.A. 2000. ILOG Solver 5.0: Reference Manual. Gentilly, France.
	18	Intelligent Systems Laboratory. 2004. SICStus Prolog user's manual, 3.11.1. Tech. rep., Swedish Institute of Computer Science, Box 1263, 164 29 Kista, Sweden.
	19	Laburthe, F. 2000. CHOCO: Implementing a CP kernel. In Proceedings of Techniques for Implementing Constraint Programming Systems (TRICS). 71--85.
	20	Lagerkvist, M. Z. and Schulte, C. 2007. Advisors for incremental propagation. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming, C. Bessière, Ed. Lecture Notes in Computer Science. Springer-Verlag, 409--422.
	21	Lhomme, O., Gotlieb, A., and Rueher, M. 1998. Dynamic optimization of interval narrowing algorithms. J. Logic Program. 37, 1--3, 165--183.
	22	Mackworth, A. K. 1977. Consistency in networks of relations. AI 8, 1, 99--118.
	23	Marriott, K. and Stuckey, P. J. 1998. Programming with Constraints: An Introduction. MIT Press, Cambridge, MA.
	24	Roger Mohr , Thomas C. Henderson, Arc and path consistence revisited, Artificial Intelligence, v.28 n.2, p.225-233, March 1986 [doi>10.1016/0004-3702(86)90083-4]
	25	Mohr, R. and Masini, G. 1988. Good old discrete relaxation. In Proceedings of the 8th European Conference on Artificial Intelligence (ECAI'88), Y. Kodratoff, Ed. Pitmann Publishing, Munich, Germany, 651--656.
	26	Eric Monfroy, Using “weaker” functions for constraint propagation over real numbers, Proceedings of the 1999 ACM symposium on Applied computing, p.553-559, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298473]
	27	Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]
	28	Mozart Consortium. 1999. The Mozart programming system. www.mozart-oz.org.
	29	Pesant, G. 2004. A regular language membership constraint for finite sequences of variables. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, M. Wallace, Ed. Lecture Notes in Computer Science, vol. 3258. Springer-Verlag, 482--495.
	30	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
	31	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
	32	Savéant, P. 2000. Constraint reduction at the type level. In Proceedings of Techniques for Implementing Constraint Programming Systems (TRICS). 16--29.
	33	Schulte, C. and Stuckey, P. J. 2004. Speeding up constraint propagation. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, M. Wallace, Ed. Lecture Notes in Computer Science, vol. 3258. Springer-Verlag, 619--633.
	34	Christian Schulte , Peter J. Stuckey, When do bounds and domain propagation lead to the same search space?, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.388-425, May 2005 [doi>10.1145/1065887.1065889]
	35	Pascal Van Hentenryck, The OPL optimization programming language, MIT Press, Cambridge, MA, 1999
	36	Van Hentenryck, P., Saraswat, V., and Deville, Y. 1991. Constraint processing in cc(FD). Draft.
	37	Van Hentenryck, P., Saraswat, V., and Deville, Y. 1998. Design, implementation and evaluation of the constraint language cc(FD). J. Logic Program. 37, 1--3, 139--164.
	38	Pascal Van Hentenryck , Helmut Simonis , Mehmet Dincbas, Constraint satisfaction using constraint logic programming, Artificial Intelligence, v.58 n.1-3, p.113-159, Dec. 1992 [doi>10.1016/0004-3702(92)90006-J]
	39	Wallace, M., Novello, S., and Schimpf, J. 1997. Eclipse: A platform for constraint logic programming. Tech. rep., IC-Parc, Imperial College, London, GB. Aug.
	40	Neng-Fa Zhou, Programming finite-domain constraint propagators in Action Rules, Theory and Practice of Logic Programming, v.6 n.5, p.483-507, September 2006 [doi>10.1017/S1471068405002590]