Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

9. Constraint-Based Local Search

Authors: Laurent Michel, Pascal Van Hentenryck

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

Abstract

Constraint-Based Local Search emerged in the last decade as a framework for declaratively expressing hard combinatorial optimization problems and solve them with local search techniques. It delivers tools to practitioners that enables them to quickly experiment with multiple models, heuristics, and meta-heuristics, focusing on their application rather than the delicate minutiae of producing a competitive implementation. At its heart, the declarative models are reminiscent of the modeling facilities familiar to constraint programming, while the underlying computational model heavily depends on incrementality. The net result is a platform capable of delivering competitive local search solutions at a fraction of the efforts needed with a conventional approach delivering model-and-run to local search users.
Literature
1.
go back to reference Borning A (1981) The programming language aspects of thinglab, a constraint-oriented simulation laboratory. ACM Trans Program Lang Syst 3(4):353–387 CrossRef Borning A (1981) The programming language aspects of thinglab, a constraint-oriented simulation laboratory. ACM Trans Program Lang Syst 3(4):353–387 CrossRef
2.
go back to reference Borning A, Duisberg R (1986) Constraint-based tools for building user interfaces. ACM Trans Comput Graph 5(4):345–374 CrossRef Borning A, Duisberg R (1986) Constraint-based tools for building user interfaces. ACM Trans Comput Graph 5(4):345–374 CrossRef
3.
go back to reference Dincbas M, Simonis H, Van Hentenryck P (1988) Solving the car sequencing problem in constraint logic programming. In: ECAI-88, Aug 1988 Dincbas M, Simonis H, Van Hentenryck P (1988) Solving the car sequencing problem in constraint logic programming. In: ECAI-88, Aug 1988
5.
go back to reference Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston/Dordrecht/London CrossRef Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston/Dordrecht/London CrossRef
7.
go back to reference Laguna M (2002) Scatter search. In: Pardalos PM, Resende MGC (eds) Handbook of applied optimization. Oxford University Press, New York, pp 183–193 Laguna M (2002) Scatter search. In: Pardalos PM, Resende MGC (eds) Handbook of applied optimization. Oxford University Press, New York, pp 183–193
8.
go back to reference Michel L (1998) Localizer: a modeling language for local search. PhD thesis, Brown University Michel L (1998) Localizer: a modeling language for local search. PhD thesis, Brown University
9.
go back to reference Michel L, Van Hentenryck P (1997) Localizer: a modeling language for local search. In: Third international conference on the principles and practice of constraint programming (CP’97), Lintz, Oct 1997 Michel L, Van Hentenryck P (1997) Localizer: a modeling language for local search. In: Third international conference on the principles and practice of constraint programming (CP’97), Lintz, Oct 1997
10.
go back to reference Minton S, Johnston MD, Philips AB (1990) Solving large-scale constraint satisfaction and scheduling problems using a Heuristic repair method. In: AAAI-90, Aug 1990 Minton S, Johnston MD, Philips AB (1990) Solving large-scale constraint satisfaction and scheduling problems using a Heuristic repair method. In: AAAI-90, Aug 1990
11.
go back to reference Myers B, Guise D, Dannenberg R, Vander Zanden B, Kosbie D, Pervin E, Mickish A, Marchal P (1990) GARNET: comprehensive support for graphical, highly interactive user interfaces. IEEE Comput 23(11):71–85 CrossRef Myers B, Guise D, Dannenberg R, Vander Zanden B, Kosbie D, Pervin E, Mickish A, Marchal P (1990) GARNET: comprehensive support for graphical, highly interactive user interfaces. IEEE Comput 23(11):71–85 CrossRef
12.
go back to reference Pham Q-D, Deville Y, Van Hentenryck P (2012) Ls(graph): a constraint-based local search for constraint optimization on trees and paths. Constraints 17(4):357–408 MathSciNetCrossRef Pham Q-D, Deville Y, Van Hentenryck P (2012) Ls(graph): a constraint-based local search for constraint optimization on trees and paths. Constraints 17(4):357–408 MathSciNetCrossRef
13.
go back to reference Selman B, Kautz H (1993) An empirical study of greedy local search for satisfiability testing. In: AAAI-93, pp 46–51 Selman B, Kautz H (1993) An empirical study of greedy local search for satisfiability testing. In: AAAI-93, pp 46–51
14.
go back to reference Selman B, Levesque H, Mitchell D (1992) A new method for solving hard satisfiability problems. In: AAAI-92, pp 440–446 Selman B, Levesque H, Mitchell D (1992) A new method for solving hard satisfiability problems. In: AAAI-92, pp 440–446
15.
go back to reference Selman B, Kautz H, Cohen B (1996) Local search strategies for satisfiability testing. In: DIMACS series in discrete mathematics and theoretical computer science, vol 26. American Mathematical Society Publications. DIMACS Selman B, Kautz H, Cohen B (1996) Local search strategies for satisfiability testing. In: DIMACS series in discrete mathematics and theoretical computer science, vol 26. American Mathematical Society Publications. DIMACS
16.
go back to reference Smith BM, Brailsford SC, Hubbard PM, Williams HP (1996) The progressive party problem: integer linear programming and constraint programming compared. Constraints 1:119–138 MathSciNetCrossRef Smith BM, Brailsford SC, Hubbard PM, Williams HP (1996) The progressive party problem: integer linear programming and constraint programming compared. Constraints 1:119–138 MathSciNetCrossRef
17.
go back to reference Sutherland IE (1963) SKETCHPAD: a man-machine graphical communication system. MIT Lincoln Labs, Cambridge CrossRef Sutherland IE (1963) SKETCHPAD: a man-machine graphical communication system. MIT Lincoln Labs, Cambridge CrossRef
20.
go back to reference Van Hentenryck P, Michel L (2005) Control abstractions for local search. Constraints 10(2):137–157 CrossRef Van Hentenryck P, Michel L (2005) Control abstractions for local search. Constraints 10(2):137–157 CrossRef
21.
go back to reference Van Hentenryck P, Michel L (2006) Differentiable invariants. In: 12th international conference on principles and practice of constraint programming (CP’06), Nantes, Sept 2006. Lecture notes in computer science Van Hentenryck P, Michel L (2006) Differentiable invariants. In: 12th international conference on principles and practice of constraint programming (CP’06), Nantes, Sept 2006. Lecture notes in computer science
22.
go back to reference Van Hentenryck P, Michel L (2007) Synthesis of constraint-based local search algorithms from high-level models. In: Proceedings of the 22nd national conference on artificial intelligence – volume 1, AAAI’07. AAAI Press, pp 273–278 Van Hentenryck P, Michel L (2007) Synthesis of constraint-based local search algorithms from high-level models. In: Proceedings of the 22nd national conference on artificial intelligence – volume 1, AAAI’07. AAAI Press, pp 273–278
23.
go back to reference Van Hentenryck P, Michel L (2009) Constraint-based local search. The MIT Press, Cambridge MATH Van Hentenryck P, Michel L (2009) Constraint-based local search. The MIT Press, Cambridge MATH
24.
go back to reference Van Hentenryck P, Michel L, Liu L (2005) Constraint-based combinators for local search. Constraints 10(3):363–384 CrossRef Van Hentenryck P, Michel L, Liu L (2005) Constraint-based combinators for local search. Constraints 10(3):363–384 CrossRef
Metadata
Title
Constraint-Based Local Search
Authors
Laurent Michel
Pascal Van Hentenryck
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_7

Premium Partner