A Mining-Based Compression Approach for Constraint Satisfaction Problems

2013/05/14 by Saïd Jabbour, Jabbour, Said, Lakhdar Saïs +3
Computer Science · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1305.3321

openalex publication_date 2013/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• On When and How to use SAT to Mine Frequent Itemsets
• From k-SAT to k-CSP: Two Generalized Algorithms
• An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints
• The Regularization of Small Sub-Constraint Satisfaction Problems
• Users Constraints in Itemset Mining