Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Configuration landscape analysis and backbone guided local search: part I: satisfiability and maximum satisfiability
Zhang W. Artificial Intelligence158 (1):1-26,2004.Type:Article
Date Reviewed: Feb 9 2005

This paper discusses the well-known nondeterministic polynomial time (NP) complete combinatorial and decision problems: the Boolean satisfiability (SAT) and the maximum satisfiability (Max-SAT = k-SAT) set of clauses of some literals (k variables) that can be set to true or false.

It is well known that local search algorithms are the most suitable techniques to solve hard SAT instances, since no known polynomial algorithm for these problems exists. However, local search algorithms are incomplete satisfaction search methods, which means that they cannot tell us there is no solution for a given SAT instance when such a solution doesn’t exist.

Zhang proposes a heuristic technique, called backbone-guided search, that improves the performance of the well-known local search algorithm WalkSAT, in solving large SAT instances. It allows the algorithm to reach a high quality local minimum, not very far from an optimal solution. Many experiments have been conducted to show the performance of the backbone heuristic with the WalkSAT local search algorithm to solve SAT instances. I think the author should compare his WalkSAT backbone with Tabu search, Ant techniques, and genetic algorithms, used successfully to solve hard SAT instances, to see if his approach is better than these techniques. In fact, WalkSAT is a relatively old technique to solve large SAT instances. I encourage the author to try to see how we can integrate his backbone heuristic with other optimization techniques.

The paper is well written and well structured. It is relatively easy to understand, even for a nonspecialist. I enjoyed reading this paper, and appreciate the efforts of the author to explain his ideas.

Reviewer:  Jihad Jaam Review #: CR130794 (0508-0947)
Bookmark and Share
 
Graph And Tree Search Strategies (I.2.8 ... )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Sorting And Searching (F.2.2 ... )
 
 
Combinatorics (G.2.1 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph And Tree Search Strategies": Date
How evenly should one divide to conquer quickly?
Walsh T. Information Processing Letters 19(4): 203-208, 1984. Type: Article
Oct 1 1985
Three approaches to heuristic search in networks
Bagchi A., Mahanti A. Journal of the ACM 32(1): 1-27, 1985. Type: Article
Sep 1 1986
AND/OR graph heuristic search methods
Mahanti A., Bagchi A. Journal of the ACM 32(1): 28-51, 1985. Type: Article
Feb 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy