Optimization on permutations: related structures, problems interrelation, heuristic compositions, applications

• Autorzy: Miatselski M.
• Języki publikacji: EN

Abstrakty

EN

A heuristics based approach to practical solving theoretically intractable combinatory and network problems is discussed. Compound heuristics (heuristics compositions) are suggested to be more efficient procedures for real size problem instances. Some aspects of the heuristics compositions topic are illustrated by optimum permutation problems. We describe a uniform presentation of the chief types of the problems and their interrelations, including the relation “to be a special case of a problem”. We consider a number of algebraic structures and combinatory constructions on permutation sets and present an inclusion chain of these constructions. The chain enables us to establish and clarify many interrelations for the minimum permutation problems, with algorithmic and complexity aspects taken into account. We also concern the applications of some problems as well.

Słowa kluczowe

EN

heuristic algorithm; heuristics composition; optimization on permutations; assignment problem; quadratic assignment problem

• Wydawca: Wydawnictwo Uniwersytetu Warmińsko-Mazurskiego w Olsztynie
• Czasopismo: Technical Sciences / University of Warmia and Mazury in Olsztyn
• Rocznik: 2018
• Tom: nr 21(1)
• Strony: 37--47
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Miatselski M.

• Katedra Informatyki i Badań Operacyjnych, Uniwersytet Warmińsko-Mazurski, ul. Słoneczna 54, 10-710 Olsztyn

Bibliografia

• BURKARD R.E., CELA E., DEMIDENKO V.M., MIATSELSKI M, WOEGINGER G.J. 1995. A unified approach to simple special cases of extremal permutation problems. Optimierung und Kontrolle. K-FU Graz, TUGraz, p 12.
• BURKARD R.E., CELA E., DEMIDENKO V.M., MIATSELSKI M., WOEGINGER G.J. 1998. A unified approach to simple special cases of extreme permutation problems. Optimization, 44: 123–138.
• CELA E. 1998 The quadratic assignment problem: Theory and algorithms. Kluwer Academic Publishers, Dordrecht, The Netherlands, p. 286.
• CHRISTOFIDES N. 1985. Graph theory: an algorithmic approach. Academic Press, p 428.
• KAMBE T., KIMURA S., INUFUSHI T., OKUDA N., NISHIOKA I. 1982. A Placement Algorithm for Polycell LSI and its Evaluation. Design Automation, 19th Conference, Las Vegas, p. 123–132.
• LAWLER E.L., LENSTRA J.K., RINNOOY KAN A.H.G., SHMOYS D.B. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.
• MIATSELSKI M. 2009. Compound heuristics as means for practical solving theoretically hard problems coming from computer-aided design. Annals of Higher School of Computer Science and Economics, Olsztyn, p. 37–46.
• REINELT G. 1994. The traveling salesman problem. Lecture Notes in Computer Science, 840: 324.
• SUPRUNENKO D.A. 1996. Permutations groups. Nauka i Technika, p. 366.
• SUPRUNENKO D.A., MIATSELSKI M.M. 1975. The assignment problem and minimization of the sum of linear forms on the symmetric group. Cybernetics and Systems, 3: 64–68.