A minimal-state processing search algorithm for satisfiability problems

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

doi:10.1109/ICSMC.2001.972986

A minimal-state processing search algorithm for satisfiability problems

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

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

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.

Original language	English
Pages (from-to)	2769-2774
Number of pages	6
Journal	Proceedings of the IEEE International Conference on Systems, Man and Cybernetics
Volume	4
DOIs	https://doi.org/10.1109/ICSMC.2001.972986
Publication status	Published - 2001

Keywords

DIMACS
Heuristic algorithm
MIPS_SAT
Optimization
SAT

ASJC Scopus subject areas

Control and Systems Engineering
Hardware and Architecture

Access to Document

10.1109/ICSMC.2001.972986

Cite this

@article{951fdea377b040f288834a27d7c36922,

title = "A minimal-state processing search algorithm for satisfiability problems",

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 = "DIMACS, Heuristic algorithm, MIPS_SAT, Optimization, SAT",

author = "Nobuo Funabiki and Tokumi Yokohira and Toru Nakanishi and Shigeto Tajima and Teruo Higashino",

year = "2001",

doi = "10.1109/ICSMC.2001.972986",

language = "English",

volume = "4",

pages = "2769--2774",

journal = "Proceedings of the IEEE International Conference on Systems, Man and Cybernetics",

issn = "0884-3627",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A minimal-state processing search algorithm for satisfiability problems

AU - Funabiki, Nobuo

AU - Yokohira, Tokumi

AU - Nakanishi, Toru

AU - Tajima, Shigeto

AU - Higashino, Teruo

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

KW - DIMACS

KW - Heuristic algorithm

KW - MIPS_SAT

KW - Optimization

KW - SAT

UR - http://www.scopus.com/inward/record.url?scp=0035719882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035719882&partnerID=8YFLogxK

U2 - 10.1109/ICSMC.2001.972986

DO - 10.1109/ICSMC.2001.972986

M3 - Article

AN - SCOPUS:0035719882

SN - 0884-3627

VL - 4

SP - 2769

EP - 2774

JO - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

JF - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

ER -

A minimal-state processing search algorithm for satisfiability problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this