Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Combinatorial search : from algorithms to systems
Hamadi Y., Springer Publishing Company, Incorporated, New York, NY, 2013. 170 pp. Type: Book (978-3-642414-81-7)
Date Reviewed: May 22 2014

The focus of this book is knowledge sharing in combinatorial search, a topic that is of considerable current importance in the quest for solutions to NP-hard problems. Operations research professionals and computer scientists alike will benefit from its clear and concise discussion of distributed and parallel search techniques for the constraint satisfaction (CSP) and propositional satisfiability (SAT) problems.

Students seeking a way into this topic will find the introduction especially helpful, particularly its treatment of the degrees of expressiveness that differentiate CSP from SAT. Chapter 2 addresses distributed CSPs and competitive and cooperative parallel search algorithms. The primary emphasis is on heterogeneous portfolios of algorithms that opportunistically exchange knowledge about problem instances, and that appear to achieve very good results. Chapter 3 applies those same concepts to centralized search, in which individual nodes or agents have full information about problem instances. Most of the chapter is devoted to the ManySAT portfolio-based parallel SAT solver, which is specifically designed to exploit multicore architectures. The next chapter takes a different approach and examines local search techniques for SAT. According to the author, the motivation for this chapter is recent progress on parallel DPLL solvers.

Chapter 5 examines methods to uncover and exploit weak dependencies among variables in order to improve solution times in CSPs, while chapter 6 takes a very different approach. In that chapter, a practical method for solving domain-specific problems is developed. In this continuous search method, an immediate solution to a problem instance is developed as needed, based on a current heuristics model (exploitation), and then the system continues to solve these instances using a set of heuristics (exploration) between consecutive arrivals of problem instances. In this way, it makes use of these gaps to improve performance on future problems.

Chapter 7 explores autonomous solvers, namely those that control their solution processes through self-adaptation (internal) processes or supervised adaptation (external) processes. An intuitive and expressive framework for characterizing these processes is presented, in addition to some open research challenges.

The final chapter provides a perspective on the previous ones and presents a keen observation for interested readers: while an optimal search strategy exists for a particular problem, determining that strategy can require much more computational power than solving the problem at hand.

This is an exceptionally well-written book, which, while primarily presenting the author’s own research, also provides a context for that work and many useful insights for the reader. Researchers, and possibly also practitioners, will find it well worth reading.

Reviewer:  Amelia Regan Review #: CR142310 (1408-0618)
Bookmark and Share
  Reviewer Selected
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Sorting And Searching (F.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorial Algorithms": Date
The complexity of combinatorial problems with succinct input representation
Wagner K. (ed) Acta Informatica 23(3): 325-356, 1986. Type: Article
Dec 1 1988
An optimal algorithm for parallel selection
Akl S. Information Processing Letters 19(1): 47-50, 1984. Type: Article
Nov 1 1985
A performance guarantee for the greedy set-partitioning algorithm
E G. J., Langston M. Acta Informatica 21(4): 409-415, 1984. Type: Article
May 1 1985
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