A variable neighborhood search for solving the linear ordering problem

  1. Carlos García González 1
  2. Dionisio Pérez Brito 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

Actas:
Proceedings of the 4th Metaheuristics International Conference (MIC'2001, Oporto)

Editorial: Editor: J. P. de Sousa

Año de publicación: 2001

Tipo: Aportación congreso

GOOGLE SCHOLAR

Resumen

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.

Referencias bibliográficas

  • 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).