A minimal-state processing search algorithm for satisfiability problems

Author

Funabiki, Nobuo ; Yokohira, Tokumi ; Nakanishi, Toru ; Tajima, Shigeto ; Higashino, Teruo

Author_Institution

Dept. of Commun. Network Eng., Okayama Univ., Japan

Volume

4

fYear

2001

fDate

2001

Firstpage

2769

Abstract

The satisfiability problem (SAT) is a typical NP-complete problem where a wide range of applications has been studied. Given a set of variables U and a set of clauses C, the goal of SAT is to find a truth assignment to variables in U such that every clause in C is satisfied if it exits, or to derive the infeasibility otherwise. This paper presents an approximation algorithm, called a minimal-state processing search algorithm for SAT (MIPS-SAT). MIPS-SAT repeatedly transits minimal states in terms of the cost function for searching a solution through a construction stage and a refinement stage. The first stage greedily generates an initial state composed of as many satisfied clauses as possible. The second stage iteratively seeks a solution while keeping state minimality. The performance of MIPS-SAT is verified through solving DIMACS benchmark instances

Keywords

approximation theory; computability; computational complexity; iterative methods; optimisation; search problems; DIMACS; NP complete problem; SAT; approximation algorithm; heuristic; iterative method; optimization; satisfiability problem; search algorithm; truth assignment; Approximation algorithms; CMOS logic circuits; Communication networks; Cost function; Heuristic algorithms; Informatics; Iterative algorithms; Lagrangian functions; Logic design; NP-complete problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Systems, Man, and Cybernetics, 2001 IEEE International Conference on

Conference_Location

Tucson, AZ

ISSN

1062-922X

Print_ISBN

0-7803-7087-2

Type

conf

DOI

10.1109/ICSMC.2001.972986

Filename

972986