STR2
STR2: optimized simple tabular reduction for table constraints. Table constraints play an important role within constraint programming. Recently, many schemes or algorithms have been proposed to propagate table constraints and/or to compress their representation. In this paper, we describe an optimization of simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of supports when generalized arc consistency (GAC) is enforced/maintained. STR2, the new refined GAC algorithm we propose, allows us to limit the number of operations related to validity checking and search of supports. Interestingly enough, this optimization makes simple tabular reduction potentially r times faster where r is the arity of the constraint(s). The results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that STR2 is usually around twice as fast as the original STR, two or three times faster than the approach based on the hidden variable encoding, and can be up to one order of magnitude faster than previously state-of-the-art (generic) GAC algorithms on some series of instances. When comparing STR2 with the more recently developed algorithm based on multi-valued decision diagrams (MDDs), we show that both approaches are rather complementary.
Keywords for this software
References in zbMATH (referenced in 10 articles )
Showing results 1 to 10 of 10.
Sorted by year (- Vion, Julien; Piechowiak, Sylvain: From MDD to BDD and arc consistency (2018)
- Carlsson, Mats; Johansson, Mikael; Larson, Jeffrey: Scheduling double round-robin tournaments with divisional play using constraint programming (2017)
- Bessiere, Christian; Fargier, Hélène; Lecoutre, Christophe: Computing and restoring global inverse consistency in interactive constraint satisfaction (2016)
- Habbas, Zineb; Amroun, Kamal; Singer, Daniel: Generalized hypertree decomposition for solving non binary CSP with compressed table constraints (2016)
- Paparrizou, Anastasia; Stergiou, Kostas: Strong local consistency algorithms for table constraints (2016)
- Lecoutre, Christophe; Likitvivatanavong, Chavalit; Yap, Roland H. C.: STR3: a path-optimal filtering algorithm for table constraints (2015)
- Lecoutre, Christophe; Likitvivatanavong, Chavalit; Yap, Roland H. C.: Improving the lower bound of simple tabular reduction (2015)
- Gent, Ian P.; Jefferson, Christopher; Linton, Steve; Miguel, Ian; Nightingale, Peter: Generating custom propagators for arbitrary constraints (2014)
- Mairy, Jean-Baptiste; van Hentenryck, Pascal; Deville, Yves: Optimal and efficient filtering algorithms for table constraints (2014)
- Lecoutre, Christophe: STR2: optimized simple tabular reduction for table constraints (2011)