STR2: optimized simple tabular reduction for table constraints |
| |
Authors: | Christophe Lecoutre |
| |
Affiliation: | 1.CRIL–CNRS UMR 8188,Université Lille-Nord de France, Artois,Lens,France |
| |
Abstract: | 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: | |
本文献已被 SpringerLink 等数据库收录! |
|