Constraint-Based Local Search (Hardcover)
暫譯: 基於約束的局部搜尋 (精裝版)

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.

Pascal Van Hentenryck is Professor in the Department of Computer Science at Brown University. He is the author or editor of several previous MIT Press books, including Principles and Practice of Constraint Programming (1995).

Laurent Michel is Assistant Professor in the Department of Computer Science and Engineering at the University of Connecticut.

 

Table of Contents:

 

Preface	xi
I	LOCAL SEARCH
1	Neighborhood Search	3
2	Heuristics and Mathematics	11
II	CONSTRAINT-BASED LOCAL SEARCH
3	Constraint-Based Local Search	29
4	Modeling	43
5	Searching	57
III	COMET
6	Invariants	85
7	Differentiable Objects	99
8	Control	139
9	First-Order Control	153
IV	APPLICATIONS
10	Tabu Search	185
11	Variable Neighborhood Search	243
12	Simulated Annealing	251
13	Guided Local Search	267
14	Hybrid Evolutionary Search	285
15	Domain-Independent Local Search	295
16	Ant Colony Optimization	311
V	SCHEDULING
17	Jobshop Scheduling	327
18	Scheduling Abstractions	337
19	Minimizing Total Tardiness in a Jobshop	345
20	Minimizing Makespan in a Jobshop	355
21	Minimizing Makespan in a Jobshop Again	377
22	Cumulative Scheduling	395
	References	407
	Index	417