A new heuristic algorithm solving the linear ordering problem. (English) Zbl 0860.90100
Summary: The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.
In the paper, we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm, we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.
In the paper, we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm, we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.
Keywords:
linear ordering problem; NP-hard combinatorial problem; heuristic algorithm; sorting through insertionReferences:
| [1] | S. Chanas, B. Florkiewicz, and M. Galant-Pater, ”Heuristic algorithms for the permutation method of the multiple attribute decision making,” Badania Operacyjne i Decyzje, Nr. 3, pp. 41–50, 1991. |
| [2] | S. Chanas, B. Florkiewicz, and M. Galant-Pater, ”Computing aspects of the permutation method in the multiple attribute decision making.” Badania Operacyjne i Decyzje, Nr. 4, pp. 5–13, 1991. |
| [3] | S. Chanas and P. Kobylański, ”Heuristic algorithm solving the problem of linear ordering,” Badania Operacyjne i Decyzje, Nr. 3, pp. 5–9, 1993. · Zbl 0860.90100 |
| [4] | M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979. · Zbl 0411.68039 |
| [5] | F. Glover, T. Klastorin, and D. Klingman, ”Optimal weighted ancestry relationships”, Management Science, vol. 20, pp. B1190-B1193, 1974. · Zbl 0303.90055 |
| [6] | M. Grötschel, M. Jünger, and G. Reinrlt, ”A cutting plane algorithm for the linear ordering problem,” Operations Research, vol. 32, no. 6, pp. 1195–1220, 1984. · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195 |
| [7] | M. Grötschel, M. Jünger, and G. Reinelt, ”On the acyclic subgraph polytope,” Mathematical Programming, vol. 33, pp. 28–42, 1985. · Zbl 0577.05034 · doi:10.1007/BF01582009 |
| [8] | Ch. Hwang and K. Yoon, ”Multiple Attribute Decision Making, Methods and Applications, A State-of-the-Art-Survey,” Lecture Notes in Economics and Mathematical Systems 186, Springer-Verlag: Berlin-Heidelberg-New York, 1981. · Zbl 0453.90002 |
| [9] | R. Kaas, ”A branch and bound algorithm for the acyclic subgraph problem,” European Journal of Operational Research, vol. 8, pp. 355–362, 1981. · Zbl 0465.90090 · doi:10.1016/0377-2217(81)90005-9 |
| [10] | B. Korte and W. Oberhofer, ”Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems,” Unternehmensforschung, vol. 12, pp. 217–231, 1968. · Zbl 0167.18403 |
| [11] | H.W. LenstraJr., ”The acyclic subgraph problem,” Report BW26 (1973), Mathematisch Centrum, Amsterdam. |
| [12] | J.K. Lenstra, ”Sequencing by enumerative methods,” Mathematical Centre Tracts 69 (1977), Mathematisch Centrum, Amsterdam. · Zbl 0407.90025 |
| [13] | P.M. Pardalos and H. Wolkowicz (Eds.), ”Quadratic Assignment and related problems,” DIMACS Series, vol. 16, American Mathematical Society, 1994. |
| [14] | H. Wessels, ”Triangulation und Blocktriangulation von Input-Output-Tabellen,” Deutsches Institut für Wirtschaftsforschung: Beiträge zur Strukturforschung, Heft 63, Berlin, 1981. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
