Title :
Datamining techniques and swarm intelligence for problem solving: Application to SAT
Author :
Drias, Habiba ; Hireche, Celia ; Douib, Ameur
Author_Institution :
Comput. Sci. Dept., USTHB, Algiers, Algeria
Abstract :
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.
Keywords :
computability; computational complexity; data mining; problem solving; swarm intelligence; NP-complete problems; SAT; bioinspired approaches; clustering clauses; complex problems; data mining techniques; meta-heuristics; problem complexity; problem solving; satisfiability problem; search area; search space; swarm intelligence; Benchmark testing; BSO; DPLL; Problem Solving; SAT; clustering; datamining techniques;
Conference_Titel :
Nature and Biologically Inspired Computing (NaBIC), 2013 World Congress on
Conference_Location :
Fargo, ND
Print_ISBN :
978-1-4799-1414-2
DOI :
10.1109/NaBIC.2013.6617862