Abstract
Table Constraints are very useful for modeling combinatorial problems in Constraint Programming (CP). They are a universal mechanism for representing constraints, but unfortunately the size of their tables can grow exponentially with their arities. In this paper, we propose to authorize entries in tables to contain simple arithmetic constraints, replacing classical tuples of values by so-called smart tuples. Smart table constraints can thus be viewed as logical combinations of those simple arithmetic constraints. This new form of tuples allows us to encode compactly many constraints, including a dozen of well-known global constraints. We show that, under a very reasonable assumption about the acyclicity of smart tuples, a Generalized Arc Consistency algorithm of low time complexity can be devised. Our experimental results demonstrate that the smart table constraint is a highly promising general purpose tool for CP.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bacchus, F., Walsh, T.: Propagating logical combinations of constraints. In: IJCAI, pp. 35–40 (2005)
Bessiere, C., Régin, J.-C.: Arc consistency for general constraint networks: preliminary results. In: Proceedings of IJCAI 1997, pp. 398–404 (1997)
Bessiere, C., Régin, J.-C.: Local consistency on conjunctions of constraints. In: Proceedings of ECAI 1998 Workshop on Non-binary constraints, pp. 53–59 (1998)
Carlson, B., Carlsson, M.: Compiling and executing disjunctions of finite domain constraints. In: Proceedings of ICLP 1995, pp. 117–131 (1995)
Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global constraints for lexicographic orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 93–108. Springer, Heidelberg (2002)
Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence 170(10), 803–834 (2006)
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)
Gent, I.P., Jefferson, C., Miguel, I., Nightingale, P.: Data structures for generalised arc consistency for extensional constraints. In: Proceedings of AAAI 2007, pp. 191–197 (2007)
Jefferson, C., Moore, N.C.A., Nightingale, P., Petrie, K.E.: Implementing logical connectives in constraint programming. Artificial Intelligence 174(16), 1407–1429 (2010)
Jefferson, C., Nightingale, P.: Extending simple tabular reduction with short supports. In: Proceedings of IJCAI 2013, pp. 573–579 (2013)
Katsirelos, G., Bacchus, F.: GAC on conjunctions of constraints. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 610–614. Springer, Heidelberg (2001)
Katsirelos, G., Walsh, T.: A compression algorithm for large arity extensional constraints. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 379–393. Springer, Heidelberg (2007)
Lecoutre, C.: Constraint Networks: Techniques and Algorithms. ISTE/Wiley (2009)
Lecoutre, C.: STR2: optimized simple tabular reduction for table constraints. Constraints 16(4), 341–371 (2011)
Lecoutre, C., Likitvivatanavong, C., Yap, R.H.C.: A path-optimal GAC algorithm for table constraints. In: Proceedings of ECAI 2012, pp. 510–515 (2012)
Lecoutre, C., Szymanek, R.: Generalized arc consistency for positive table constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 284–298. Springer, Heidelberg (2006)
Lhomme, O.: Arc-consistency filtering algorithms for logical combinations of constraints. In: Régin, J.-C., Rueher, M. (eds.) CPAIOR 2004. LNCS, vol. 3011, pp. 209–224. Springer, Heidelberg (2004)
Lhomme, O.: Practical reformulations with table constraints. In: Proceedings of ECAI 2012, pp. 911–912 (2012)
Lhomme, O., Régin, J.-C.: A fast arc consistency algorithm for n-ary constraints. In: Proceedings of AAAI 2005, pp. 405–410 (2005)
Mackworth, A.K., Freuder, E.C.: The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial intelligence 25(1), 65–74 (1985)
Mairy, J.-B., Van Hentenryck, P., Deville, Y.: Optimal and efficient filtering algorithms for table constraints. Constraints 19(1), 77–120 (2014)
Meseguer, P., Torras, C.: Solving strategies for highly symmetric CSPs. In: Proceedings of IJCAI 1999, pp. 400–405 (1999)
Nightingale, P., Gent, I.P., Jefferson, C.A., Miguel, I.J.: Short and long supports for constraint propagation. Journal of Artificial Intelligence Research 46, 1–45 (2013)
Perez, G., Régin, J.-C.: Improving GAC-4 for table and MDD constraints. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 606–621. Springer, Heidelberg (2014)
Régin, J.-C.: Improving the expressiveness of table constraints. In: Proceedings of CP 2011 Workshop on Constraint Modelling and Reformulation (2011)
Simonis, H., O’Sullivan, B.: Search strategies for rectangle packing. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 52–66. Springer, Heidelberg (2008)
Ullmann, J.R.: Partition search for non-binary constraint satisfaction. Information Sciences 177(18), 3639–3678 (2007)
Van Hentenryck, P., Saraswat, V., Deville, Y.: Design, implementation, and evaluation of the constraint language cc(fd). The Journal of Logic Programming 37(1–3), 139–164 (1998)
Würtz, J., Müller, T.: Constructive disjunction revisited. In: Görz, G., Hölldobler, S. (eds.) KI 1996. LNCS, vol. 1137, pp. 377–386. Springer, Heidelberg (1996)
Xia, W., Yap, R.H.C.: Optimizing STR algorithms with tuple compression. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 724–732. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Mairy, JB., Deville, Y., Lecoutre, C. (2015). The Smart Table Constraint. In: Michel, L. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science(), vol 9075. Springer, Cham. https://doi.org/10.1007/978-3-319-18008-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-18008-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18007-6
Online ISBN: 978-3-319-18008-3
eBook Packages: Computer ScienceComputer Science (R0)