Received 25.05.2022; Revised 31.05.2022; Accepted 28.06.2022

Published 30.06.2022; First Online 03.08.2022

https://doi.org/10.34229/2707-451X.22.1.1

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

UDC 519.8

On Some Optimization Problems on Permutations

Georgy Donets ,   Vasyl Biletskyi

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Numerous studies consider combinatorial optimization problems and their solution methods, since a large number of practical problems are described by means of combinatorial optimization models. Among these problems, the most prominent ones are function optimization problems on combinatorial configurations. Many of the studies mentioned above propose approaches and describe methods to solve combinatorial optimization problems for linear and fractionally linear functions on combinatorial sets such as permutations and arrangements.

This work describes new approaches and methods to solve some maximization problems for linear, fractionally linear and quadratic functions on permutation set. Algorithms for solving these problems are given.

 For linear function, we provide a considerably easy method to find the permutation on which the function attains its maximum value.

 We describe the general algorithm to find fractionally linear function maximum. We consider the cases in which variables of numerator and denominator do not intersect, and when the numerator function and the denominator function have one common variable. We also describe the case in which the numerator function and the denominator function in total have incomplete variable list, i.e. when the total quantity of variables is less than the quantity of numbers in the permutation set.

As for solving the problem of finding quadratic function maximum on permutation set, it turned out that there is no universal algorithm to solve this problem for any quadratic function. In this paper, we describe a method of finding maximum on permutation set for quadratic function consisting of two items.

We provide examples of solving the considered optimization problems.

 

Keywords:  function, permutation, set, transposition, coefficients.

 

Cite as: Donets G., Biletskyi V. On Some Optimization Problems on Permutations. Cybernetics and Computer Technologies. 2022. 1. P. 5–10. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.1.1

 

References

           1.     Donets G.A., Kolechkina L.N. Extremal Problems on Combinatorial Configurations. Poltava: RVV PUET, 2011. 309 p. (in Ukrainian) http://dspace.uccu.org.ua/handle/123456789/560

           2.     Donets G.A., Kolechkina L.N. Method of ordering the values of a linear function on a set of permutations. Cybern Syst Anal. 2009. 45 (2). P. 204–213. https://doi.org/10.1007/s10559-009-9092-6

           3.     Donets G.A., Kolechkina L.N. On one Problem of Optimization of a Linear Fractional Function on Permutations. Journal of Automation and Information Sciences. 2010. 42 (4). P. 1–12. https://doi.org/10.1615/JAutomatInfScien.v42.i4.10

           4.     Semenova N.V., Kolechkina L.N., Nagirna A.N. An approach to solving discrete vector optimization problems over a combinatorial set of permutations. Cybern Syst Anal. 2008. 44 (3). P. 441–451. https://doi.org/10.1007/s10559-008-9016-x

           5.     Yemets O.O., Yemets E.M., Olhovskiy D.M. The Method of Cutting the Vertices of Permutation Polyhedron Graph to Solve Linear Conditional Optimization Problems on Permutations. Cybernetics and Systems Analysis. 2014. 50. P. 613–619. https://doi.org/10.1007/s10559-014-9649-x

           6.     Koliechkina L.N., Dvernaya O.A., Nagornaya A.N. Modified Coordinate Method to Solve Multicriteria Optimization Problems on Combinatorial Configurations. Cybernetics and Systems Analysis. 2014. 50. P. 620–626. https://doi.org/10.1007/s10559-014-9650-4

           7.     Iemets O.O., Kolechkina L.N. Problems of Combinatorial Optimization with Linear Fractional Objectives. Kyiv: Naukova Dumka, 2005. 117 p. (in Ukrainian)

           8.     Gantmacher F.К. Theory of matrices. M.: Nauka, 1967. 575 p.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next