Mining to Compress Table Constraints

In this paper, we propose an extension of our mining-based SAT compression framework to constraint satisfaction problem (CSP). We consider n-ary extensional constraints (table constraints). Our approach aims to reduce the size of the CSP by exploiting the structure of the constraints graph and its associated microstructure. More precisely, we apply itemset mining techniques to search for closed frequent itemsets on these two representations. Using Tseitin extension, we rewrite the whole CSP to another compressed CSP equivalent with respect to satisfiability. Our approach contrasts with the previous proposed technique by Katsirelos and Walsh, as it does not change the inner-structure of the constraints. Experiments on some CSP instances show that our approach can achieve interesting compression rate.