IslandSAT

摘要

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, DLMI. DLMI2004 and ESG1, 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.