CONSTRAINT-BASED LOCAL SEARCH

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 thesechallenging 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.