Research Of Optimizing Simple Tabular Reduction With Adaptive Compression Method

Constraint Programming(CP)is a general and flexible framework for modeling and solving combinatorial constrained problems.Table constraints,also called extensional constraints,explicitly express the allowed combinations of values for the variables they involve as sequences of tuples,which are called tables.Table constraints can theoretically encode any kind of constraints and are among the most useful ones in Constraint Programming.These constraints can be generated from data that has been read from a database in a configuration problem,or may encode users' preferences,among other applications.Table constraints define an arbitrary constraint explicitly as a set of solutions(tuples)or non-solutions.Thus,space is proportional to number of tuples.Simple Tabular Reduction(STR),which dynamically reduces the table size by maintaining a table of only the valid tuples,has been shown to be efficient for enforcing GAC.The STR2 and STR3 algorithms based on its optimized version are the state-of-the-art GAC algorithms,STR2 and STR3 have advantages in different types of instances.A big improvement in the domain is the use of bit vectors in table constraints to represent the validity of tuples,and efficient bitwise parallel operations when looking for support for variable values.Both the STRbit and Compact-Table algorithms combine the advantages of STR and bit vector operations and have been shown to be an order of magnitude faster than the best GAC algorithms developed over the past decade.Table constraints have one major drawback: the memory space required to store them may grow exponentially with the number of arities.To solve this problem,various table compression methods have been proposed.When the table size is enough large,the appropriate table compression method can not only greatly reduce the space consumption,but also greatly improve the time overhead of the GAC algorithm.Short support and Cartesian product representation are the two most common table compression methods on table constraints.The constraint table can be compressed by Cartesian product representation.This compression method is first used in symmetric break and nogoods learning.Using tuples The Cartesian product representation compresses the table constraint and calls it a c-tuple.We use full-length tuples to represent short supports,with a special symbol * indicating when a variable is not contained in the short support,which means that some variables can take any value in the domain.Using these two compression methods to optimize STR2 to obtain the table compression algorithms shortSTR2 and STR2-C respectively,we found that the compression ratio is the main reason that affects the optimization on the same problem for the two table compression methods.In this paper,we propose an adaptive table compression method.By comparing the compression ratio of the two table compression methods,we choose the table compression method with large compression ratio.We apply the adaptive table compression method to the algorithm STR2,and we propose the STR2-Adaptive algorithm,which covering the advantages of both table compression methods.The experimental results show that STR2-Adaptive can choose the best table compression method on most of the problems,and the additional time cost is only about 1%,which maximizes the optimization of STR2 algorithm.Furthermore,we extend the adaptive table compression method to the algorithm STRbit and propose the STRbit-Adaptive algorithm,which combines the efficient bitwise operations.The experiment shows that the STRbit-Adaptive algorithm can also improve the running speed of the STRbit algorithm on most problems.