Abstract
We present an extension to indexicals to describe propagators for global constraints. The resulting language is compiled into actual propagators for different solvers, and is solver-independent. In addition, we show how this high-level description eases the proof of propagator properties, such as correctness and monotonicity. Experimental results show that propagators compiled from their indexical descriptions are sometimes not significantly slower than built-in propagators of Gecode. Therefore, our language can be used for the rapid prototyping of new global constraints.
This work is supported by grant 2011-6133 of the Swedish Research Council (VR). We thank the anonymous reviewers and Christian Schulte for their useful comments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Achterberg, T.: SCIP: Solving constraint integer programs. Mathematical Programming Computation 1, 1–41 (2009)
Ågren, M., Flener, P., Pearson, J.: Inferring Variable Conflicts for Local Search. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 665–669. Springer, Heidelberg (2006)
Beldiceanu, N., Carlsson, M., Flener, P., Pearson, J.: On the reification of global constraints. Tech. Rep. T2012:02, Swedish Institute of Computer Science (February 2012), http://soda.swedish-ict.se/view/sicsreport/
Beldiceanu, N., Carlsson, M., Rampon, J.X.: Global constraint catalog, 2nd edn. (revision a). Tech. Rep. T2012:03, Swedish Institute of Computer Science (February 2012), http://soda.swedish-ict.se/view/sicsreport/
Carlson, B., Carlsson, M., Diaz, D.: Entailment of finite domain constraints. In: Proceedings of ICLP 1994, pp. 339–353. MIT Press (1994)
Carlsson, M., Ottosson, G., Carlson, B.: An Open-Ended Finite Domain Constraint Solver. In: Glaser, H., Hartel, P., Kuchen, H. (eds.) PLILP 1997. LNCS, vol. 1292, pp. 191–206. Springer, Heidelberg (1997)
CHOCO: An open source Java CP library, http://www.emn.fr/z-info/choco-solver/
Choi, C.W., Lee, J.H.M., Stuckey, P.J.: Removing propagation redundant constraints in redundant modeling. ACM Transactions on Computational Logic 8(4) (2007)
Dao, T.B.H., Lallouet, A., Legtchenko, A., Martin, L.: Indexical-Based Solver Learning. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 541–555. Springer, Heidelberg (2002)
Dynadec, Dynamic Decision Technologies Inc.: Comet tutorial, v2.0 (2009), http://dynadec.com/
Frühwirth, T.W.: Theory and practice of constraint handling rules. Journal of Logic Programming 37(1-3), 95–138 (1998)
Gecode Team: Gecode: A generic constraint development environment (2006), http://www.gecode.org/
Gent, I.P., Jefferson, C., Miguel, I.: Watched Literals for Constraint Propagation in Minion. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 182–197. Springer, Heidelberg (2006)
JaCoP: Java constraint programming solver, http://jacop.osolpro.com/
Mohr, R., Henderson, T.: Arc and path consistency revisited. Artificial Intelligence 28, 225–233 (1986)
Ohrimenko, O., Stuckey, P., Codish, M.: Propagation via lazy clause generation. Constraints 14, 357–391 (2009)
Parr, T.J.: Enforcing strict model-view separation in template engines. In: Proceedings of the 13th International Conference on the World Wide Web, pp. 224–233. ACM (2004)
Parr, T.J.: The Definitive ANTLR Reference: Building Domain-Specific Languages. The Pragmatic Bookshelf (2007)
Régin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of AAAI 1994, pp. 362–367. AAAI Press (1994)
Richaud, G., Lorca, X., Jussien, N.: A portable and efficient implementation of global constraints: The tree constraint case. In: Proceedings of CICLOPS 2007, pp. 44–56 (2007)
Scampi (2011), https://bitbucket.org/pschaus/scampi/
Schulte, C., Stuckey, P.J.: Speeding Up Constraint Propagation. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 619–633. Springer, Heidelberg (2004)
Sidebottom, G., Havens, W.S.: Nicolog: A simple yet powerful cc(FD) language. Journal of Automated Reasoning 17, 371–403 (1996)
Tack, G., Schulte, C., Smolka, G.: Generating Propagators for Finite Set Constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 575–589. Springer, Heidelberg (2006)
Van Hentenryck, P., Deville, Y.: The cardinality operator: A new logical connective for constraint logic programming. In: Proceedings of ICLP 1991, pp. 745–759 (1991)
Van Hentenryck, P., Michel, L.: Differentiable Invariants. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 604–619. Springer, Heidelberg (2006)
Van Hentenryck, P., Saraswat, V., Deville, Y.: Design, implementation, and evaluation of the constraint language cc(FD). Tech. Rep. CS-93-02, Brown University, Providence, USA (January 1993), revised version in Journal of Logic Programming 37(1-3), 293–316 (1998). Based on the unpublished manuscript Constraint Processing in cc(FD) (1991)
Zhou, N.F.: Programming finite-domain constraint propagators in action rules. Theory and Practice of Logic Programming 6, 483–507 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Monette, JN., Flener, P., Pearson, J. (2012). Towards Solver-Independent Propagators. In: Milano, M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-33558-7_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33557-0
Online ISBN: 978-3-642-33558-7
eBook Packages: Computer ScienceComputer Science (R0)