Constraint-Based Local Search. 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.

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 72 articles , 1 standard article )

Showing results 41 to 60 of 72.
Sorted by year (citations)
  1. Chabert, Gilles; Jaulin, Luc: Contractor programming (2009)
  2. Dooms, Grégoire; Van Hentenryck, Pascal; Michel, Laurent: Model-driven visualizations of constraint-based local search (2009)
  3. Grossmann, Ignacio E.; Furman, Kevin C.: Challenges in enterprise wide optimization for the process industries (2009)
  4. Michel, Laurent; See, Andrew; van Hentenryck, Pascal: Parallel and distributed local search in COMET (2009)
  5. Michel, Laurent; See, Andrew; Van Hentenryck, Pascal: Transparent parallelization of constraint programming (2009)
  6. Schrijvers, Tom; Stuckey, Peter; Wadler, Philip: Monadic constraint programming (2009)
  7. Van Hentenryck, Pascal; Coffrin, Carleton; Gutkovich, Boris: Constraint-based local search for the automatic generation of architectural tests (2009) ioport
  8. Bautista, Joaquín; Pereira, Jordi; Adenso-Díaz, Belarmino: A GRASP approach for the extended car sequencing problem (2008)
  9. di Tollo, Giacomo; Roli, Andrea: Metaheuristics for the portfolio selection problem (2008)
  10. Estellon, Bertrand; Gardi, Frédéric; Nouioua, Karim: Two local search approaches for solving real-life car sequencing problems (2008)
  11. Marriott, Kim; Nethercote, Nicholas; Rafeh, Reza; Stuckey, Peter J.; Garcia de la Banda, Maria; Wallace, Mark: The design of the zinc modelling language (2008)
  12. Mehlhorn, Kurt; Sanders, Peter: Algorithms and data structures. The basic toolbox (2008)
  13. Meyer, Bernd: Hybrids of constructive metaheuristics and constraint programming: a case study with ACO (2008)
  14. Solnon, Christine: Combining two pheromone structures for solving the car sequencing problem with ant colony optimization (2008)
  15. Solnon, Christine; Cung, Van Dat; Nguyen, Alain; Artigues, Christian: The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem (2008)
  16. Ågren, Magnus; Flener, Pierre; Pearson, Justin: Generic incremental algorithms for local search (2007)
  17. Beldiceanu, Nicolas; Carlsson, Mats; Demassey, Sophie; Petit, Thierry: Global constraint catalogue: past, present and future (2007)
  18. Dooms, Grégoire; Van Hentenryck, Pascal; Michel, Laurent: Model-driven visualizations of constraint-based local search (2007) ioport
  19. Liu, Hsiao-Fei; Chao, Kun-Mao: A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering (2007)
  20. Sabato, Sivan; Naveh, Yehuda: Preprocessing expression-based constraint satisfaction problems for stochastic local search (2007)