×

zbMATH — the first resource for mathematics

Improving the lower bound of simple tabular reduction. (English) Zbl 1316.90026
Summary: Simple Tabular Reduction (STR) is a state-of-the-art filtering technique for enforcing Generalized Arc Consistency (GAC) on positive table constraints. Despite its good performance in practice, the STR2 algorithm suffers from a mandatory lower bound equal to the number of domain values in the current state of the problem, because the presence of each value must be justified every time STR2 is called. We overcome this fixed cost by redesigning STR2 and incorporating watched tuples. Experiments show that the revised algorithm is better at coping with problems that involve a large number of small changes during search and it can be more than twice as fast on certain structured problems.
Reviewer: Reviewer (Berlin)

MSC:
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
STR2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Briggs, P; Torczon, L, An efficient representation for sparse sets, ACM Letters on Programming Languages and Systems, 2, 59-69, (1993)
[2] Cheng, KCK; Yap, RHC, An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, Constraints, 15, 265-304, (2010) · Zbl 1204.68188
[3] Gange, G; Stuckey, PJ; Szymanek, R, MDD propagators with explanation, Constraints, 16, 407-429, (2011) · Zbl 1241.90066
[4] Jefferson, C., & Nightingale, P. (2013). Extending simple tabular reduction with short supports. In Proceedings of IJCAI-13 (pp. 573-579). · Zbl 1244.90232
[5] Lecoutre, C, STR2: optimized simple tabular reduction for table constraints, Constraints, 16, 341-371, (2011) · Zbl 1244.90232
[6] Lecoutre, C., Likitvivatanavong, C., Yap, R.H.C. (2012). A path-optimal GAC algorithm for table constraints. In Proceedings of ECAI-12 (pp. 510-515). · Zbl 1327.68220
[7] Lecoutre, C., Paparrizou, A., Stergiou, K. (2013). Extending STR to a higher-order consistency. In Proceedings of AAAI-13 (pp. 576-582).
[8] Likitvivatanavong, C., Zhang, Y., Shannon, S., Bowen, J., Freuder, E.C. (2007). Arc consistency during search. In Proceedings of IJCAI-07 (pp. 137-142). · Zbl 1241.90066
[9] Mairy, J.-B., Hentenryck, P.V., Deville, Y. (2012). An optimal filtering algorithm for table constraints. In Proceedings of CP-12 (pp. 496-511).
[10] Ullmann, JR, Partition search for non-binary constraint satisfaction, Information Science, 177, 3639-3678, (2007) · Zbl 1119.68446
[11] Xia, W., & Yap, R.H.C. (2013). Optimizing STR algorithm with tuple compression. In Proceedings of CP-13 (pp. 724-732).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.