The Multi-SAT algorithm Original Research Article

Many efficient algorithms have been developed for satisfiability testing. They complement rather than exclude each other by being effective for particular problem instances. In this research, we give a Multi-SAT algorithm for the SAT problem. The Multi-SAT algorithm integrates several efficient SAT algorithms. It makes use of different algorithmic niches for satisfiability testing. Based on cost-effective cluster computing, Multi-SAT can perform simultaneous satisfiability testing, using several “stones” to shoot one “bird”. The software architecture for Multi-SAT has been designed. A number of software tools have been developed. This software tool kit can support efficient satisfiability testing with uncertain problem structure, facilitating multiple tracking of an algorithm structure, and allow a detailed study of the entire problem spectrum. It provides a cost-effective multi-tool kit for practical satisfiability testing.