|
Review
"Van Hentenryck and Michel provide a long-overdue synthesis of work in local search. This is supported by the
development of a programming language that is optimized for local search and the use of this language to solve numerous difficult
problems previously addressed by ad hoc heuristics and general-purpose metaheuristics. Their book will be a valuable addition
to the literature for both students and researchers."
—John W. Chinneck, Professor, Systems and Computer Engineering,
Carleton University, Ottawa
"Constraint-Based Local Search presents a powerful new programming language paradigm
for combinatorial optimization, uniting the power of local search with the declarativeness of constraint programming. This
book will become an important reference for students and practitioners of combinatorial optimization."
—Andrew J.
Davenport, IBM T. J. Watson Research Center
Product Description
The ubiquity of combinatorial optimization
problems in our society is illustrated by the novel application areas for optimization technology, which range from supply
chain management to sports tournament scheduling. Over the last two decades, constraint programming has emerged as a fundamental
methodology to solve a variety of combinatorial problems, and rich constraint programming languages have been developed for
expressing and combining constraints and specifying search procedures at a high level of abstraction. Local search approaches
to combinatorial optimization are able to isolate optimal or near-optimal solutions within reasonable time constraints.
This
book introduces a method for solving combinatorial optimization problems that combines constraint programming and local search,
using constraints to describe and control local search, and a programming language, COMET, that supports both modeling and
search abstractions in the spirit of constraint programming.
After an overview of local search including neighborhoods,
heuristics, and metaheuristics, the book presents the architecture and modeling and search components of constraint-based
local search and describes how constraint-based local search is supported in COMET. The book describes a variety of applications,
arranged by meta-heuristics. It presents scheduling applications, along with the background necessary to understand these
challenging problems. The book also includes a number of satisfiability problems, illustrating the ability of constraint-based
local search approaches to cope with both satisfiability and optimization problems in a uniform fashion.
|
