Compact SAT-based Encoding Of Mining Minimal Non Redundant Association Rules
Abdelhamid Boudane, Riyadh Ouzghara · 2024
Propositional logic is widely used for solving combinatorial problems by employing logical constraints on boolean variables. One frequently used constraint is AtMostOne $\left({{{\sum olimits_{i = 1}^n x }_i} \leq 1}\right)$, which ensures that at most one variable in a set of boolean variables can be true. Existing encodings focus on translating individual AtMostOne constraints into boolean formulas. However, in practical applications, multiple overlapping AtMostOne constraints often need to be encoded together. This separate encoding approach can lead to redundant sub-formulas and increased resolution times. In this paper, we identify how sequential counter-based encodings generate redundant sub-formulas and propose an algorithm to optimize the encoding size for sets of overlapping AtMostOne constraints. We implement this approach to tackle a data mining problem, specifically extracting non-redundant association rules from transactional data. Through experiments on various datasets, we demonstrate that our method produces more concise encodings and significantly reduces enumeration times.