Authors: Yousef Kilani; Mohammad Bsoul; Ibrahim Obeidat; Mamoun Al-Rababaa
Addresses: Faculty of Prince Al-Hussein Bin Abdallah II for Information Technology, Hashemite University, Jordan ' Faculty of Prince Al-Hussein Bin Abdallah II for Information Technology, Hashemite University, Jordan ' Faculty of Prince Al-Hussein Bin Abdallah II for Information Technology, Hashemite University, Jordan ' Prince Hussein bin Abdullah Faculty of Information Technology, Al Al-Bayt University, Mafraq, Jordan
Abstract: The satisfiability (SAT) problem, as one of the six basic core NP-complete problems, has been the deserving object of many studies in the last two decades. Stochastic local search algorithms (SLSA) are one of the current state-of-the-art techniques for solving the SAT problems. Kilani and Fang et al. introduced the island confinement method (ICM) for reducing the search space in SLSA. They incorporate this idea into two SLSA: DLM and ESG. Their new algorithms, DLMIr, DLMI2004 and ESGI, show far better results than DLM and ESG respectively after the incorporation process. In this research, we create a stand-alone solver, IslandSAT solver, based on the ICM that is independent of any SLSA. We show through experimentation that IslandSAT is competitive to DLMI2004 and far better than ESGI. Furthermore, we find that Island-SAT is competitive to the state-of-the-art SLSA, TNM and adaptg2wsat2009++, for solving the SAT problems.
Keywords: island confinement method; ICM; local search algorithms; IslandSAT solver; satisfiability; NP-complete problems.
International Journal of Advanced Intelligence Paradigms, 2012 Vol.4 No.3/4, pp.278 - 298
Received: 07 Jul 2012
Accepted: 29 Oct 2012
Published online: 23 Aug 2014 *