A variable neighborhood search for solving the linear ordering problem
-
1
Universidad de La Laguna
info
Publisher: Editor: J. P. de Sousa
Year of publication: 2001
Type: Conference paper
Abstract
A Systematic change of Neighborhood within a possibly randomized local search algorithm yields asimple and effective metaheuristic for combinatorial and global optimization. In this paper we presenta Variable Neighborhood Search implementation designed to find high quality solutions for the NP-hardLinear Ordering Problem, which has a significant number of application in practice, such triangulationof input-output matrices, archeological seriation, minimizing total weighted completion time in onemachine scheduling, and aggregation of individual preferences.We perform our implementation on the set of 49 instances in LOLIB, in order to compare our results with the Tabu Search of Laguna, et al.
Bibliographic References
- S. Chanas and P. Kobylanski. A New Heuristic Algorithm Solving the Linear Ordering Problem. Computational Optimization and Applications, vol. 6,pp. 191-205. (1996).
- F. Glover. Tabu Search-Part I. ORSA Journal on Computing, 1, pp. 190-206. (1989).
- F. Glover. Tabu Search-Part II. ORSA Journal on Computing, 2, pp. 4-32. (1990).
- F. Glover and M. Laguna. Tabu Search In C. Reeves, editor, Modern Heuristic techniques for combinatorial problems (chapter 3), Oxford: Blackwell. (1993).
- F. Glover and M. Laguna. Tabu Search. Kluwer Academic Plublishers, Boston. (1997).
- M. Grotschel, M. Junger and G. Reinelt. A Cutting Plane Algorithm for the Linear Ordering Problem. Operation Reseach, vol.32, no 6, pp. 1195-1220. (1984).
- P. Hansen and N. Mladenovic. An Introduction to Variable Neighborhood Search. In S. Voss et al., editors, Proceeding of the 2nd International Conference on Metaheurists-MIC97, Kluwer, Dordrecht. (1998).
- S. Kirkpatrick, C.D. Gelatt Jr. y M.P. Vecchi. Optimization by Simulated Annealing. Science, 220, 671-680. (1983).
- M. Laguna, R. Mart´ın and V. Campos. Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem. Computer and Operation Research, vol 26, pp. 1217- 1230. (1999).
- N. Mladenovic. Variable neighborhood algorithm -a new meta-heuristic for combinatorial optimization. Presented at Optimization days 1995, pp22, Montreal, Canada.
- N. Mladenovic and P. Hansen. Variable neighborhood search. Computers and Operations Research. Vol. 24 pp. 1097-1100, (1997).
- P. Hansen and N. Mladenovic. An Introduction to Variable Neighborhood Search in S. Voss et al., editors, Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, pp. 433–458, Kluwer, Dordrecht, (1999).
- LOLIB (1997) http://www.iwr.uni-heildelberg.de/iwr/comopt/soft/LOLIB/LOLIB.html
- P. Hansen and N. Mladenovic. The Linear Ordering Problem: Algorithms and Applications. In H. H. Hofmann and R. Wille, editors, Research and Exposition in Mathematics, Vol. 8. (1985).