Abstract
Local search is a traditional technique to solve combinatorial search problems which has raised much interest in recent years. The design and implementation of local search algorithms is not an easy task in general and may require considerable experimentation and programming effort. However, contrary to global search, little support is available to assist the design and implementation of local search algorithms. This paper is an attempt to support the implementation of local search. It presents the preliminary design of LOCALIZER, a modeling language which makes it possible to express local search algorithms in a notation close to their informal descriptions in scientific papers. Experimental results on our first implementation show the feasibility of the approach.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
R. Fourer, D. Gay, and B.W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, San Francisco, CA, 1993.
F. Glover. Tabu Search. Orsa Journal of Computing, 1:190–206, 1989.
D. Johnson, C. Aragon, L. McGeoch, and C. Schevon. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, 39(3):378–406, 1991.
S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by Simulated Annealing. Science, 220:671–680, 1983.
S. Minton, M.D. Johnston, and A.B. Philips. Solving Large-Scale Constraint Satisfaction and Scheduling Problems using a Heuristic Repair Method. In AAAI-90, August 1990.
C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982.
B. Selman and H. Kautz. An Empirical Study of Greedy Local Search for Satisfiability Testing. In AAAI-93, pages 46–51, 1993.
B. Selman, H. Levesque, and D. Mitchell. A New Method for Solving Hard Satisfiability Problems. In AAAI-92, pages 440–446, 1992.
P. Stuckey and V. Tam. Models for Using Stochastic Constraint Solvers in Constraint Logic Programming. In PLILP-96, Aachen, August 1996.
P. Van Hentenryck, L. Michel, and Y. Deville. Numerica: a Modeling Language for Global Optimization. The MIT Press, Cambridge, Mass., 1997.
C. Voudouris and E. Tsang. Partial Constraint Satisfaction Problems and Guided Local Search. In PACT-96, London, April 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Michel, L., Van Hentenryck, P. (1997). Localizer A modeling language for local search. In: Smolka, G. (eds) Principles and Practice of Constraint Programming-CP97. CP 1997. Lecture Notes in Computer Science, vol 1330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017443
Download citation
DOI: https://doi.org/10.1007/BFb0017443
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63753-0
Online ISBN: 978-3-540-69642-1
eBook Packages: Springer Book Archive