Variable neighborhood search for minimum linear arrangement problem
DOI:
https://doi.org/10.2298/YJOR140928038MKeywords:
graphs, optimization, minimum linear arrangement problem, variable neighborhood searchAbstract
The minimum linear arrangement problem is widely used and studied in many practical and theoretical applications. It consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. This problem is one among the classical NP-hard optimization problems and therefore there has been extensive research on exact and approximative algorithms. In this paper we present an implementation of a variable neighborhood search (VNS) for solving minimum linear arrangement problem. We use Skewed general VNS scheme that appeared to be successful in solving some recent optimization problems on graphs. Based on computational experiments, we argue that our approach is comparable with the state-of-the-art heuristic.References
Aarts E. H. and Korst J. H., Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, John Wiley and Sons, 1989.
Aarts E. H. and Laarhoven P. J. V., “Statistical cooling: A general approach to combinatorial optimization problem”, Philips Journal of Research, 40 (1985) 193–226.
Adolphson D. and Hu T. C., “Optimal linear ordering“, SIAM Journal on Applied Mathematics, 25(3) (1973) 403–423.
Bar-Yehuda R., Even G., Feldman J., and Naor J., “Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems“, Journal of Graph Algorithms and Applications, 5(4) (2001) 1–27.
Beasley J., “OR-library: distributing test problems by electronic mail”, Journal of the Operational Research Society, 41 (1990) 1069-1072. Available at: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files.
Boese K. D. and Kahng A. B., “Best-so-far vs. where-you-are: Implications for optimal finite-time annealing”, Systems and Control Letters, 22(1) (1994) 71–78.
Brimberg J., Mladenović N., Urošević D., “Solving the maximally diverse grouping problem by skewed general variable neighborhood search”, Information Sciences, 295 (2015) 650–675, http://dx.doi.org/10.1016/j.ins.2014.10.043.
Brimberg J., Janićijević S., Mladenović N., Urošević D., “Solving the Clique Partitioning Problem as a Maximally Diverse Grouping Problem” (submitted for publication).
Charon I. and Hudry O., “The noising method: A new method for combinatorial optimization”, Operations Research Letters, 14(3) (1993) 133–137.
Diaz J., Petit J., and Serna M., “A survey of graph layout problems”, ACM Computing Surveys, 34(3) (2002) 313–356.
Daskin M., Network and Discrete Location: Models, Algorithms, and Applications, Wiley, 1995.
Domínguez-Marín P., The Discrete Ordered Median Problem: Models and Solution Methods, PhD thesis, University of Kaiserslautern, 2003.
Domínguez-Marín P., Nickel S., Hansen P., and Mladenović N., “Heuristic procedures for solving the discrete ordered median problem”, Annals of Operations Research, 136 (2005) 145–173.
Drezner Z. and Hamacher H., Facility Location: Applications and Theory, Springer Berlin Heidelberg New York, 2002.
Falkenauer E., “A hybrid grouping genetic algorithm for bin packing”, Journal of Heuristics, 2 (1996) 5–30.
Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, 1979.
Hanafi S., Lazic J., Mladenović N., Wilbaut C., Crevits I., “New VNS based 0-1 MIP Heuristics”, Yugoslav Journal of Operations Research, DOI: 10.2298/YJOR140219014H.
Harper L. H., “Optimal assignment of numbers to vertices”, SIAM Journal on Applied Mathematics, 12(1) (1964) 131–135.
Hansen P. and Mladenović N., “Variable neighborhood search for the p-median”, Location Science, 5(4) (1997) 207–226.
Hansen P. and Mladenović N., Developments of Variable Neighborhood Search, In C. C. Ribeiro and P. Hansen, editors, Essays and Surveys in Metaheuristics, pages 415–439, Kluwer Academic Publishers, 2001.
Hansen P. and Mladenović N., “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, 130(3) (2001) 449–467.
Hansen P. and Mladenović N., Variable Neighborhood Search, In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, International Series in Operations Research & Management Science, 57, Boston, MA: Kluwer Academic Publishers, 2003.
Hansen P., Mladenović N. and Pérez-Brito D., “Variable Neighborhood Decomposition Search”, Journal of Heuristics, 7 (2001) 335–350.
Hansen P., Mladenović N. and Moreno Pérez J. A., “Variable neighborhood search: methods and applications”, Annals of Operations Research, 175 (2010) 367–407.
Ilić A., Urošević D., Brimberg J., Mladenović N., “Variable neighborhood search for solving the uncapacitated single allocation p-hub median problem”, European Journal of Operational Research, 206 (2010) 289–300.
Juvan M. and Mohar B., “Optimal linear labelings and eigenvalues of graphs”, Discrete Applied Mathematics, 36(2) (1992) 153–168.
Kritzinger S., Doerner K. F., Tricoire F., Hartl R. F., “Adaptive search techniques for problems in vehicle routing, Part I: A survey”, Yugoslav Journal of Operations Research, DOI: 10.2298/YJOR140219014H.
Kritzinger S., Doerner K. F., Tricoire F., Hartl R. F., “Adaptive search techniques for problems in vehicle routing, Part II: A numerical comparison”, Yugoslav Journal of Operations Research, DOI: 10.2298/YJOR140217011K.
McAllister A. J., “A new heuristical algorithm for the linear arrangement problem”, Technical Report TR-99-126a, Faculty of Computer Science, University of New Brunswick.
Mladenović N., Todosijević R. and Urošević D., “An efficient General variable neighborhood search for large TSP problem with time windows”, Yugoslav Journal of Operations Research, 22 (2012) 141–151.
Mladenović N., Urošević D., Pérez-Brito D. and García-González C. G., “Variable neighborhood search for bandwidth reduction”, European Journal of Operational Research, 200 (2010) 14–27.
Pantrigo J. J., Duarte A., Campos V. and Martí R., “Heuristic for Minimum Linear Arrangement Problem”, Working Paper.
Petit J., “Experiments on the minimum linear arrangement problem”, ACM Journal of Experimental Algorithmics, 8 (2003).
Petit J., “Combining spectral sequencing and parallel simulated annealing for the MinLA problem”, Parallel Processing Letters, 13(1) (2003) 77–91.
Reinelt G., Seitz H., “On a binary distance model for the minimum linear arrangement problem”, TOP, DOI: 10.1007/s11750-012-0263-7.
Rodriguez-Tello E., Hao J.-K., and Torres-Jimenez J., “Memetic algorithms for the MinLA problem”, Lecture Notes in Computer Science, 3871 (2006) 73–84.
Rodriguez-Tello E., Hao J., Torres-Jimenez J., “An Effective Two-Stage Simulated Annealing Algorithm for the Minimum Linear Arrangement Problem”, Computers and Operations Research, 35(10) (2008) 3331–3346.
Todosijević R., Mladenović N., Urošević D., Hanafi S., “A general variable neighborhood search for solving the uncapacitated r-allocation p-hub median problem” (to appear).
Urošević D., Brimberg J., Mladenović N., “Variable neighborhood decomposition search for the edge weighted k–cardinality tree problem”, Computers & Operations Research, 31(8) (2004) 1205–1213.
Urošević D., “Variable neighborhood search for Maximum diverse grouping problem”, Yugoslav Journal of Operations Research, 24 (1) (2014) 21–33.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
