A Mining-Based Compression Approach for Constraint Satisfaction Problems
This work addresses efficiency in solving CSPs for researchers and practitioners, but it is incremental as it builds on existing mining techniques and focuses on a specific constraint type.
The paper tackles the problem of reducing the size of Constraint Satisfaction Problems (CSPs) by extending a Mining for SAT framework to CSPs with n-ary extensional constraints, resulting in a compressed CSP equivalent in satisfiability without altering the constraint structure.
In this paper, we propose an extension of our Mining for SAT 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 of its associated microstructure. More precisely, we apply itemset mining techniques to search for closed frequent itemsets on these two representation. Using Tseitin extension, we rewrite the whole CSP to another compressed CSP equivalent with respect to satisfiability. Our approach contrast with previous proposed approach by Katsirelos and Walsh, as we do not change the structure of the constraints.