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 47 articles , 1 standard article )

Showing results 1 to 20 of 47.
Sorted by year (citations)

1 2 3 next

  1. Cire, Andre A.; Hooker, John N.; Yunes, Tallys: Modeling with metaconstraints and semantic typing of variables (2016)
  2. Shishmarev, Maxim; Mears, Christopher; Tack, Guido; Garcia de la Banda, Maria: Visual search tree profiling (2016)
  3. Björdal, Gustav; Monette, Jean-Noël; Flener, Pierre; Pearson, Justin: A constraint-based local search backend for MiniZinc (2015)
  4. Caniou, Yves; Codognet, Philippe; Richoux, Florian; Diaz, Daniel; Abreu, Salvador: Large-scale parallelism for constraint-based local search: the costas array case study (2015)
  5. Schrijvers, Tom; Demoen, Bart; Triska, Markus; Desouter, Benoit: Tor: modular search with hookable disjunction (2014)
  6. Ansótegui, Carlos; Bofill, Miquel; Palahí, Miquel; Suy, Josep; Villaret, Mateu: Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories (2013)
  7. Schrijvers, Tom; Tack, Guido; Wuille, Pieter; Samulowitz, Horst; Stuckey, Peter J.: Search combinators (2013)
  8. Hermenegildo, M.V.; Bueno, F.; Carro, M.; López-García, P.; Mera, E.; Morales, J.F.; Puebla, G.: An overview of Ciao and its design philosophy (2012)
  9. Pham, Quang Dung; Deville, Yves; van Hentenryck, Pascal: LS(graph): a constraint-based local search for constraint optimization on trees and paths (2012)
  10. Benoist, Thierry; Estellon, Bertrand; Gardi, Frédéric; Megel, Romain; Nouioua, Karim: LocalSolver 1.x: A black-box local-search solver for 0-1 programming (2011)
  11. He, Jun; Flener, Pierre; Pearson, Justin: An automaton constraint for local search (2011)
  12. Katsirelos, George; Narodytska, Nina; Walsh, Toby: The weighted grammar constraint (2011)
  13. Monette, Jean-Noël: Solving scheduling problems from high-level models (2011)
  14. Puchinger, Jakob; Stuckey, Peter J.; Wallace, Mark G.; Brand, Sebastian: Dantzig-Wolfe decomposition and branch-and-price solving in G12 (2011)
  15. Shaw, Paul: Constraint programming and local search hybrids (2011)
  16. Bay, Maud; Crama, Yves; Langer, Yves; Rigo, Philippe: Space and time allocation in a shipyard assembly Hall (2010)
  17. Gualandi, Stefano; Malucelli, Federico; Sozzi, Domenico L.: On the design of the next generation access networks (2010)
  18. Hebrard, Emmanuel; O’Mahony, Eoin; O’Sullivan, Barry: Constraint programming and combinatorial optimisation in Numberjack (2010)
  19. Khichane, Madjid; Albert, Patrick; Solnon, Christine: Strong combination of ant colony optimization with constraint programming optimization (2010)
  20. Milano, Michela; Wallace, Mark: Integrating operations research in constraint programming (2010)

1 2 3 next