Abstract
In this paper the linear Ordering Problem (LOP) is approached. This problem consists in to find an ordering of rows and columns of a matrix weights, such that the sum of all the values above the main diagonal is minimized. We propose in this ongoing research, increases the efficiency of exploration method in the insertion neighborhood in the state of the art Tabu search solution. The approach is evaluated on the broad set of standard instances that include the most difficult XLOLIB instances, from which the optima values are unknown. The results for instances which optimum values are known (OI), show that the proposed method has obtained reductions in execution time ranging between 21% and 97%, while, for the most difficult instances included in the set with unknown optima (BI), the reduction reaching 98%.Wilcoxon test is used to prove that the proposed method ITS, obtains similar % average error for OI instances than the reference method RTS, and a significance reduction in the average time. Now we are working in developing additional diversification strategies that take advantage of the savings in time to explore new regions of the search space.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Becker, O.: Das Helmstädtersche Reihenfolge problem die Effizienz Verschiedener Näherungsverfahren in Computer uses in the Social Sciences. In: Berichteiner Working Conference, Wien (1967)
Campos, V., Glover, F., Laguna, M., Martí, R.: An experimental evaluation of a scatter search for the linear ordering problem. J. of Global Optimization 21, 397–414 (2001); Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Dordrecht (1997)
Chanas, S., Kobylanski, P.: A New Heuristic Algorithm Solving the Linear Ordering Problem, Computational Optimization and Applications (1996)
Chenery, H., Watanabe, T.: International Comparisons of the Structure of Production. Econometrica 26, 4 (1958)
Chiarini, B.: New algorithm for the triangulation of input-output tables and the linear ordering problem, University of Florida (2004)
Congram, R.: Polynomially Searchable Exponential Neighbourhoods for Sequencing Problems in Combinatorial Optimization, University of Southampton, Faculty of Mathematical Studies, PhD Thesis, EEUU (2000)
Duarte, A., Pantrigo, J., Gallego, M.: Metaheurísticas. Madrid, España, Dykinson (2007)
Garcia, C.G., Pérez-Brito, D., Campos, V., Martí, R.: Variable neighborhood search for the linear ordering problem. Computers and Operations Research 33, 3549–3565 (2006)
Garey, M.R., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1975)
Glover, F.: Tabu search and adaptive memory programming-Advances, applications and challenges. In: Barr, R.S., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization and Stochastic Modeling Technologies, pp. 1–75. Kluwer, Boston (1997)
Laguna, M., Martí, R., Campos, V.: Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem. Computers and Operations Research 26, 1217–1230 (1999)
Leontief, W.: Input-Output Economics. Oxford University Press, New York (2004)
Schiavinotto, T., Stützle, T.: The linear ordering problem: Instances, search space analysis and algorithms. Journal of Mathematical Modelling and Algorithms 3(4), 367–402 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Ingram, F.E.G., Valdez, G.C., Huacuja, H.J.F. (2010). Using Consecutive Swaps to Explore the Insertion Neighborhood in Tabu Search Solution of the Linear Ordering Problem. In: Melin, P., Kacprzyk, J., Pedrycz, W. (eds) Soft Computing for Recognition Based on Biometrics. Studies in Computational Intelligence, vol 312. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15111-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-15111-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15110-1
Online ISBN: 978-3-642-15111-8
eBook Packages: EngineeringEngineering (R0)