Research On Constraint Propagation Algorithms On Table Constraints

Table constraints define an arbitrary constraint relation explicitly as a set of supported or forbidden tuples on a group of variables.Generalized Arc Consistency(GAC)is the most widely used consistency for solving non-binary constraint satisfaction problems(CSPs).Simple Tabular Reduction(STR)enforces GAC on table constraints.Based on the idea of dynamically maintaining valid part of constraint relations,STR removes invalid tuples each time enforcing GAC,thus reduce the cost of collecting supports for variables.When a backtrack occurs,STR restores constraint relations in constant time.Many variants of STR are proposed and some of them improve the performance by using a compressed representation of constratins relations.In this paper,we propose STR2* sharing the same idea of STR which dynamically maintains valid part of constraint relations.However,constraint relations are stored by columns,and the operations of deleting invalid tuples and updating supports for variables are converted into corresponding column-wise operations.Besides,STR2* uses time stamps to record the order of operations on variables and constraints,which reduces the cost of collecting variables whose domain has been changed and simplifies data structure appeared in STR algorithms.Experimental evaluations show that our algorithm outperforms existing STR algorithms without compression representation of relations.In some classes of problems,our algorithm is even more efficient than state-of-the-art compression representation based STR algorithms.MDDc,STR2 and STR3 all enforce GAC on table constraints.MDDc represents constraint relations as a set of multi-valued diagrams(MDD).When a MDD has many identical parts,the compression ratio is high and MDDc outperforms others.STR2 uses tables to represent constraint relations.When enforcing GAC,STR2 iterates current table to collect valid tuples and projects these tuples onto variables to update supports.STR3 uses dual tables to represents constraint relations.Each value of a variable maintains a copy of tuples including this value.When enforcing GAC,each value updates its supports by iterating its own copy of tuples.When the set of valid tuples decrease slowly,STR3 outperforms STR2.Otherwise,STR2 outperforms STR3.Our analyzation shows that collecting valid outgoing edges for a node in a MDD and deleting invalid tuples in a dual table are always the most time-consuming operations respectively in MDDc and STR3.Thus,we propose AdaptiveMDDc and AdaptiveSTR respectively for MDDc and STR3,which perform the above two operations in an adaptive way.AdaptiveMDDc collects valid outgoing edges adaptively according to the size of current valid part of graphs.AdaptiveSTR deletes invalid tuples adaptively according to the size of current valid part of tables.The results show that both algrithms always employ the lowest cost implementations in different stages of search.Benefiting from its lower cost of strategy chosen and the significant performance difference of each implementation during search,AdaptiveMDDc and AdaptiveSTR have better performance compared to the original ones and adaptiveSTR is over three times faster than STR3 in some instances besides.