×

STR3: a path-optimal filtering algorithm for table constraints. (English) Zbl 1328.68199

Summary: Constraint propagation is a key to the success of constraint programming (CP). The principle is that filtering algorithms associated with constraints are executed in sequence until quiescence is reached. Many such algorithms have been proposed over the years to enforce the property called generalized arc consistency (GAC) on many types of constraints, including table constraints that are defined extensionally. Recent advances in GAC algorithms for extensional constraints rely on directly manipulating tables during search. This is the case with a simple approach called simple tabular reduction (STR), which systematically maintains tables of constraints to their relevant lists of tuples. In particular, STR2, a refined STR variant is among the most efficient GAC algorithms for positive table constraints. In this paper, we revisit this approach by proposing a new GAC algorithm called STR3 that is specifically designed to enforce GAC during backtrack search. By indexing tables and reasoning from deleted values, we show that STR3 can avoid systematically iterating over the full set of current tuples, contrary to STR2. An important property of STR3 is that it can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. We also study a variant of STR3, based on an optimal circular way for traversing tables, and discuss the relationship of STR3 with two other optimal GAC algorithms introduced in the literature, namely, GAC4 and AC5TC-Tr. Finally, we demonstrate experimentally how STR3 is competitive with the state-of-the-art. In particular, our extensive experiments show that STR3 is generally faster than STR2 when the average size of tables is not reduced too drastically during search, making STR3 complementary to STR2.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

INGRES; STR2; Chaff
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lecoutre, C.; Likitvivatanavong, C.; Yap, R. H.C., A path-optimal GAC algorithm for table constraints, (Proceedings of ECAI-12. Proceedings of ECAI-12, Montpellier, France (2012)), 510-515 · Zbl 1327.68220
[2] Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 1, 99-118 (1977) · Zbl 0341.68061
[3] Mohr, R.; Henderson, T. C., Arc and path consistency revisited, Artif. Intell., 28, 2, 225-233 (1986)
[4] Mohr, R.; Masini, G., Good old discrete relaxation, (Proceedings of ECAI-88. Proceedings of ECAI-88, Munich, Germany (1988)), 651-656
[5] Sabin, D.; Freuder, E. C., Contradicting conventional wisdom in constraint satisfaction, (Proceedings of CP’94. Proceedings of CP’94, Orcas Island, USA (1994)), 10-20
[6] Bessière, C.; Régin, J.-C., Arc consistency for general constraint networks: preliminary results, (Proceedings of IJCAI-97. Proceedings of IJCAI-97, Nagoya, Japan (1997)), 398-404
[7] Lhomme, O.; Régin, J.-C., A fast arc consistency algorithm for \(n\)-ary constraints, (Proceedings of AAAI-05. Proceedings of AAAI-05, Pittsburgh, Pennsylvania (2005)), 405-410
[8] Lecoutre, C.; Szymanek, R., Generalized arc consistency for positive table constraints, (Proceedings of CP-06. Proceedings of CP-06, Nantes, France (2006)), 284-298 · Zbl 1335.90096
[9] Bessière, C.; Régin, J.-C.; Yap, R. H.C.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artif. Intell., 165, 2, 165-185 (2005) · Zbl 1132.68691
[10] Ullmann, J. R., Partition search for non-binary constraint satisfaction, Inf. Sci., 177, 18, 3639-3678 (2007) · Zbl 1119.68446
[11] Lecoutre, C., STR2: optimized simple tabular reduction for table constraints, Constraints, 16, 4, 341-371 (2011) · Zbl 1244.90232
[12] Cheng, K. C.K.; Yap, R. H.C., An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, Constraints, 15, 2, 265-304 (2010) · Zbl 1204.68188
[13] Gent, I. P., Optimal implementation of watched literals and more general techniques, J. Artif. Intell. Res., 48, 231-252 (2013) · Zbl 1277.68247
[14] Mairy, J.-B.; Hentenryck, P. V.; Deville, Y., An optimal filtering algorithm for table constraints, (Proceedings of CP-12. Proceedings of CP-12, Quebec City, Canada (2012)), 496-511
[15] Sabin, D.; Freuder, E. C., Contradicting conventional wisdom in constraint satisfaction, (Proceedings of ECAI-94. Proceedings of ECAI-94, Amsterdam, The Netherlands (1994)), 125-129
[16] Stonebraker, M.; Held, G.; Wong, E.; Kreps, P., The design and implementation of INGRES, ACM Trans. Database Syst., 1, 3, 189-222 (1976)
[17] Astrahan, M. M.; Blasgen, M. W.; Chamberlin, D. D.; Eswaran, K. P.; Gray, J. N.; Griffiths, P. P.; King, W. F.; Lorie, R. A.; McJones, P. R.; Mehl, J. W.; Putzolu, G. R.; Traiger, I. L.; Wade, B. W.; Watson, V., System R: relational approach to database management, ACM Trans. Database Syst., 1, 2, 97-137 (1976)
[18] Briggs, P.; Torczon, L., An efficient representation for sparse sets, ACM Lett. Program. Lang. Syst., 2, 1-4, 59-69 (1993)
[19] le Clément de Saint-Marcq, V.; Schauss, P.; Solnon, C.; Lecoutre, C., Sparse-sets for domain implementation, (Proceedings of CP-13 Workshop on Techniques for Implementing Constraint Programming Systems. Proceedings of CP-13 Workshop on Techniques for Implementing Constraint Programming Systems, TRICS-13, Uppsala, Sweden (2013))
[20] Gange, G.; Stuckey, P. J.; Lagoon, V., Fast set bounds propagation using a BDD-SAT hybrid, J. Artif. Intell. Res., 38, 307-338 (2010) · Zbl 1210.68100
[21] Gent, I. P.; Jefferson, C.; Miguel, I.; Nightingale, P., Data structures for generalised arc consistency for extensional constraints, (Proceedings of AAAI-07. Proceedings of AAAI-07, Vancouver, Canada (2007)), 191-197
[22] Cheng, K. C.K.; Yap, R. H.C., Maintaining generalized arc consistency on ad hoc \(n\)-ary boolean constraints, (Proceedings of ECAI-06. Proceedings of ECAI-06, Trento, Italy (2006)), 78-82
[23] Likitvivatanavong, C.; Zhang, Y.; Shannon, S.; Bowen, J.; Freuder, E. C., Arc consistency during search, (Proceedings of IJCAI-07. Proceedings of IJCAI-07, Hyderabad, India (2007)), 137-142
[24] Likitvivatanavong, C.; Zhang, Y.; Bowen, J.; Freuder, E. C., Arc consistency in MAC: a new perspective, (Proceedings of CP-04 Workshop on Constraint Propagation and Implementation. Proceedings of CP-04 Workshop on Constraint Propagation and Implementation, CPAI-04, Toronto, Canada (2004)), 93-108
[25] Moskewisz, M. W.; Madigan, C. F.; Zhao, Y.; Zhang, L.; Malik, S., Chaff: engineering an efficient SAT solver, (Proceedings of DAC-2001. Proceedings of DAC-2001, Las Vegas, NV (2001)), 530-535
[26] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), The MIT Press · Zbl 1187.68679
[27] Hentenryck, P. V.; Deville, Y.; Teng, C., A generic arc-consistency algorithm and its specializations, Artif. Intell., 57, 2-3, 291-321 (1992) · Zbl 0763.68059
[28] Bessière, C.; Cordier, M.-O., Arc-consistency and arc-consistency again, (Proceedings of AAAI-93. Proceedings of AAAI-93, Washington, DC (1993)), 108-113
[29] Bessière, C.; Freuder, E. C.; Régin, J.-C., Using constraint metaknowledge to reduce arc consistency computation, Artif. Intell., 107, 1, 125-148 (1999) · Zbl 0911.68192
[30] Becker, C.; Fargier, H., Maintaining alternative values in constraint-based configuration, (Proceedings of IJCAI-13. Proceedings of IJCAI-13, Beijing, China (2013)), 454-460
[31] Mairy, J.-B.; Hentenryck, P. V.; Deville, Y., Optimal and efficient filtering algorithms for table constraints, Constraints, 19, 1, 77-120 (2014) · Zbl 1328.68201
[32] Lecoutre, C.; Likitvivatanavong, C.; Shannon, S. G.; Yap, R. H.C.; Zhang, Y., Maintaining arc consistency with multiple residues, Constraint Program. Lett., 2, 3-19 (2008)
[33] Boussemart, F.; Hemery, F.; Lecoutre, C.; Sais, L., Boosting systematic search by weighting constraints, (Proceedings of ECAI’04. Proceedings of ECAI’04, Valencia, Spain (2004)), 146-150
[34] Amilhastre, J.; Fargier, H.; Marquis, P., Consistency restoration and explanations in dynamic CSPs — application to configuration, Artif. Intell., 135, 1-2, 199-234 (2002) · Zbl 0983.68182
[35] Pesant, G.; Quimper, C.-G.; Zanarini, A., Counting-based search: branching heuristics for constraint satisfaction problems, J. Artif. Intell. Res., 43, 173-210 (2012) · Zbl 1237.68193
[36] Xia, W.; Yap, R. H.C., Optimizing STR algorithm with tuple compression, (Proceedings of CP-13. Proceedings of CP-13, Uppsala, Sweden (2013)), 724-732
[37] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artif. Intell., 171, 8-9, 514-534 (2007) · Zbl 1168.68554
[38] Katsirelos, G.; Walsh, T., A compression algorithm for large arity extensional constraints, (Proceedings of CP-07. Proceedings of CP-07, Providence, Rhode Island (2007)), 379-393
[39] Cheng, K. C.K.; Yap, R. H.C., Maintaining generalized arc consistency on ad hoc \(r\)-ary constraints, (Proceedings of CP-08. Proceedings of CP-08, Sydney, Australia (2008)), 509-523
[40] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 3, 353-366 (1989) · Zbl 0665.68084
[41] Rossi, F.; Petrie, C.; Dhar, V., On the equivalence of constraint satisfaction problems, (Proceedings of ECAI’90. Proceedings of ECAI’90, Stockholm, Sweden (1990)), 550-556
[42] Stergiou, K.; Walsh, T., Encodings of non-binary constraint satisfaction problems, (Proceedings of AAAI’99. Proceedings of AAAI’99, Orlando, Florida (1999)), 163-168
[43] Lecoutre, C.; Vion, J., Enforcing arc consistency using bitwise operations, Constraint Program. Lett., 2, 21-35 (2008)
[44] Lecoutre, C.; Hemery, F., A study of residual supports in arc consistency, (Proceedings of IJCAI-07. Proceedings of IJCAI-07, Hyderabad, India (2007)), 125-130
[45] Lecoutre, C.; Paparrizou, A.; Stergiou, K., Extending STR to a higher-order consistency, (Proceedings of AAAI-13. Proceedings of AAAI-13, Washington, US (2013)), 576-582
[46] Jefferson, C.; Nightingale, P., Extending simple tabular reduction with short supports, (Proceedings of IJCAI-13. Proceedings of IJCAI-13, Beijing, China (2013)), 573-579
[47] Bessière, C.; Fargier, H.; Lecoutre, C., Global inverse consistency for interactive constraint satisfaction, (Proceedings of CP-13. Proceedings of CP-13, Uppsala, Sweden (2013)), 159-174
[48] Gharbi, N.; Hemery, F.; Lecoutre, C.; Roussel, O., Sliced table constraints: combining compression and tabular reduction, (Proceedings of CPAIOR-14. Proceedings of CPAIOR-14, Cork, Ireland (2014)), 120-135 · Zbl 1407.68450
[49] Lecoutre, C.; Likitvivatanavong, C.; Yap, R. H.C., Improving the lower bound of simple tabular reduction, Constraints (2015) · Zbl 1316.90026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.