Combinatorial Search: From Algorithms to Systems

Authors: Hamadi, Youssef

  • Summarizes the state of the art and proposes a clear architecture for solver and autonomous solvers
  • Case studies translate the theoretical ideas into real-world applications
  • Valuable for researchers and practitioners working on optimization, complexity theory, search, and constraints
see more benefits

Buy this book

eBook $84.99
price for USA (gross)
  • ISBN 978-3-642-41482-4
  • Digitally watermarked, DRM-free
  • Included format: PDF, EPUB
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $109.00
price for USA
  • ISBN 978-3-642-41481-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $109.00
price for USA
  • ISBN 978-3-662-51429-0
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

Although they are believed to be unsolvable in general, tractability results suggest that some practical NP-hard problems can be efficiently solved. Combinatorial search algorithms are designed to efficiently explore the usually large solution space of these instances by reducing the search space to feasible regions and using heuristics to efficiently explore these regions. Various mathematical formalisms may be used to express and tackle combinatorial problems, among them the constraint satisfaction problem (CSP) and the propositional satisfiability problem (SAT). These algorithms, or constraint solvers, apply search space reduction through inference techniques, use activity-based heuristics to guide exploration, diversify the searches through frequent restarts, and often learn from their mistakes.

In this book the author focuses on knowledge sharing in combinatorial search, the capacity to generate and exploit meaningful information, such as redundant constraints, heuristic hints, and performance measures, during search, which can dramatically improve the performance of a constraint solver. Information can be shared between multiple constraint solvers simultaneously working on the same instance, or information can help achieve good performance while solving a large set of related instances. In the first case, information sharing has to be performed at the expense of the underlying search effort, since a solver has to stop its main effort to prepare and commu

nicate the information to other solvers; on the other hand, not sharing information can incur a cost for the whole system, with solvers potentially exploring unfeasible spaces discovered by other solvers. In the second case, sharing performance measures can be done with little overhead, and the goal is to be able to tune a constraint solver in relation to the characteristics of a new instance – this corresponds to the selection of the most suitable algorithm for solving a given instance.

The book is suitable for researchers, practitioners, and graduate students working in the areas of optimization, search, constraints, and computational complexity.

About the authors

Dr. Youssef Hamadi is the head of the Constraint Reasoning Group at Microsoft Research Cambridge, and his research interests include combinatorial optimization in alternative frameworks (parallel and distributed architectures); the application of machine learning to search; autonomous search; and parallel propositional satisfiability.

Reviews

“The book deals with combinatorial search algorithms for NP-hard problems, focusing on knowledge sharing in combinatorial search. … The diversity and originality of the proposed methods could be helpful for researchers, practitioner and graduate students working in optimization, search, and computational complexity.” (Smaranda Belciug, zbMATH 1317.68003, 2015)

“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. … 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.” (Amelia Regan, Computing Reviews, May, 2014)

“The main purpose of this book is to describe several aspects of combinatorial search algorithms and systems in a unified manner. … The book is well written and will be useful for researchers and graduate students in computer science, operations research, and applied mathematics.” (Petrica Pop, Computing Reviews, January, 2014)


Table of contents (8 chapters)

Buy this book

eBook $84.99
price for USA (gross)
  • ISBN 978-3-642-41482-4
  • Digitally watermarked, DRM-free
  • Included format: PDF, EPUB
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $109.00
price for USA
  • ISBN 978-3-642-41481-7
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $109.00
price for USA
  • ISBN 978-3-662-51429-0
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Combinatorial Search: From Algorithms to Systems
Authors
Copyright
2013
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-642-41482-4
DOI
10.1007/978-3-642-41482-4
Hardcover ISBN
978-3-642-41481-7
Softcover ISBN
978-3-662-51429-0
Edition Number
1
Number of Pages
XIII, 139
Number of Illustrations and Tables
14 b/w illustrations, 16 illustrations in colour
Topics