Constraint-Based Local Search (Hardcover)

B. Behan

  • 出版商: Palgrave Macmillan
  • 出版日期: 2011-07-15
  • 定價: $2,100
  • 售價: 6.0$1,260
  • 語言: 英文
  • 頁數: 175
  • 裝訂: Hardcover
  • ISBN: 0262220776
  • ISBN-13: 9780262220774

立即出貨

買這商品的人也買了...

相關主題

商品描述

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