Abstract
The linear ordering problem consists of finding an acyclic tournament in a complete weighted digraph of maximum weight. It is one of the classical NP-hard combinatorial optimization problems. This paper surveys a collection of heuristics and metaheuristic algorithms for finding near-optimal solutions and reports about extensive computational experiments with them. We also present the new benchmark library LOLIB which includes all instances previously used for this problem as well as new ones.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achatz, H., Kleinschmidt, P., Lambsdorff, J.: Der Corruption Perceptions Index und das Linear Ordering Problem. ORNews 26, 10–12 (2006)
Aujac, H.: La hiérarchie des industries dans un tableau des echanges industriels. Rev. Econ. 2, 169–238 (1960)
Becker, O.: Das Helmstädtersche Reihenfolgeproblem – die Effizienz verschiedener Näherungsverfahren. In: Computer Uses in the Social Sciences, Bericht einer Working Conference des Inst. f. höh. Studien u. wiss. Forsch. Wien (1967)
Boenchendorf, K.: Reihenfolgenprobleme/Mean-Flow-Time Sequencing. Mathematical Systems in Economics, vol. 74. Verlagsgruppe Athenäum, Hain, Scriptor, Königstein (1982)
Campos, V., Glover, F., Laguna, M., Martí, R.: An experimental evaluation of a scatter search for the linear ordering problem. J. Glob. Optim. 21, 397–414 (2001)
Chanas, S., Kobylanski, P.: A new heuristic algorithm solving the linear ordering problem. Comput. Optim. Appl. 6, 191–205 (1996)
Charon, I., Hudry, O.: A survey on the linear ordering problem for weighted or unweighted tournaments. 4OR 5, 5–60 (2007)
Chenery, H.B., Watanabe, T.: International comparisons of the structure of production. Econometrica 26, 487–521 (1958)
Christof, T.: Low-dimensional 0/1-Polytopes and Branch-and-Cut in Combinatorial Optimization. Shaker, Aachen (1997)
Christof, T., Reinelt, G.: Combinatorial optimization and small polytopes. Top 4, 1–64 (1996)
Condorcet, M.J.A.N.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785), Paris
Feo, T., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 2, 1–27 (1995)
Garcia, C.G., Pérez-Brito, D., Campos, V., Martí, R.: Variable neighborhood search for the linear ordering problem. Comput. Oper. Res. 33, 3549–3565 (2006)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986)
Glover, F., Klastorin, T., Klingman, D.: Optimal weighted ancestry relationships. Manag. Sci. 20, 1190–1193 (1974)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1997)
Goemans, M.X., Hall, L.A.: The strongest facets of the acyclic subgraph polytope are unknown. In: Proc. of the 5th Int. IPCO Conference. LNCS, vol. 1084, pp. 415–429. Springer, Berlin (1996)
Grötschel, M., Jünger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32, 1195–1220 (1984)
Huang, G., Lim, A.: Designing a hybrid genetic algorithm for the linear ordering problem. In: Cantu-Paz, E., et al. (eds.) Proc. of Genetic and Evolutionary Computation—GECCO 2003. LNCS, vol. 2723, pp. 1053–1064. Springer, Berlin (2003)
Hansen, P., Mladenovic, N.: Variable neighborhood search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 145–184 (2003)
Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1, 1–25 (1997)
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291–308 (1979)
Knuth, D.E.: The Stanford GraphBase: A Platform for Combinatorial Computing. Addison-Wesley, Reading (1993)
Laguna, M., Martí, R., Campos, V.: Intensification and diversification with elite tabu search solutions for the linear ordering problem. Comput. Oper. Res. 26, 1217–1230 (1999)
Laguna, M., Martí, R.: Scatter Search: Methodology and Implementations in C. Kluwer Academic, Dordrecht (2003)
Leontief, W.: Quantitative input-output relations in the economic system of the United States. Rev. Econ. Stat. 18, 105–125 (1936)
Martí, R., Reinelt, G.: The Linear Ordering Problem: Exact and Heuristics Methods in Combinatorial Optimization. Applied Mathematical Sciences, vol. 175. Springer, Berlin (2010)
Mitchell, J.E., Borchers, B.: Solving linear ordering problems. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.) High Performance Optimization. Applied Optimization, vol. 33, pp. 340–366. Kluwer Academic, Dordrecht (2000)
Reinelt, G.: The Linear Ordering Problem: Algorithms and Applications. Research and Exposition in Mathematics, vol. 8. Heldermann, Berlin (1985)
Ribeiro, C.C., Uchoa, E., Werneck, R.F.: A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J. Comput. 14, 228–246 (2002)
Schiavinotto, T., Stützle, T.: The linear ordering problem: instances, search space analysis and algorithms. J. Math. Model. Algorithms 3, 367–402 (2004)
Author information
Authors and Affiliations
Corresponding author
Electronic Supplementary Material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Martí, R., Reinelt, G. & Duarte, A. A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput Optim Appl 51, 1297–1317 (2012). https://doi.org/10.1007/s10589-010-9384-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-010-9384-9