Datamining techniques and swarm intelligence for problem solving: Application to SAT

摘要

Solving NP-complete problems is one of the most important research areas nowadays. Several studies have been held to shed the light on these complex problems and on the satisfiability problem especially. Exact methods being limited by time and space, bio-inspired approaches and meta-heuristics have been developed to overcome this drawback. The effectiveness of these methods is based on the judicious exploration of the search area, which is not always obvious, especially for large problem instances. Our work consists in proposing an alternative to this issue by considering data mining techniques to explore the search space before solving the instance. The idea is to reduce the complexity of the problem by clustering clauses and hence variables and afterwards solving the clusters with a smaller number of variables.