2020, issue 2, p. 14-18
Received 04.06.2020; Revised 14.06.2020; Accepted 30.06.2020
Published 24.07.2020; First Online 27.07.2020
https://doi.org/10.34229/2707-451X.20.2.2
Previous | Full text (in Russian) | Next
On the Problem of a Linear Function Localization on Permutations
G.A.
Donets 
,
V.I. 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.
Combinatorial optimization problems and methods of their solution have been a subject of numerous studies, since a large number of practical problems are described by combinatorial optimization models. Many studies consider approaches to and describe methods of solution for combinatorial optimization problems with linear or fractionally linear target functions on combinatorial sets such as permutations and arrangements. Studies consider solving combinatorial problems by means of well-known methods, as well as developing new methods and algorithms of searching a solution.
We describe a method of solving a problem of a linear target function localization on a permutation set. The task is to find those locally admissible permutations on the permutation set, for which the linear function possesses a given value. In a general case, this problem may have no solutions at all.
In the article, we propose a newly developed method that allows us to obtain a solution of such a problem (in the case that such solution exists) by the goal-oriented seeking for locally admissible permutations with a minimal enumeration that is much less than the number of all possible variants.
Searching for the solution comes down to generating various permutations and evaluating them. Evaluation of each permutation includes two steps. The first step consists of function decreasing by transposing the numbers in the first n – 3 positions, and the second step is evaluation of the permutations for the remaining three numbers. Then we analyze the correlation (which is called balance) to define whether the considered permutation is the solution or not.
In our article, we illustrate the localization method by solving the problem for n = 5.
Keywords: localization, linear function, permutation, transposition, balance, position.
Cite as: Donets G.A., Biletskyi V.I. On the Problem of a Linear Function Localization on Permutations. Cybernetics and Computer Technologies. 2020. 2. P. 14–18. (in Russian) https://doi.org/10.34229/2707-451X.20.2.2
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. Iemets 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. Cybern Syst Anal. 2014. 50 (4). 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. Cybern Syst Anal. 2014. 50 (4). 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. Iemets O.O., Barabolina T.N. Combinatorial Optimization on Allocations. Kyiv: Naukova Dumka, 2008. 159 p. (in Russian)
9. Iemets O.O., Chernenko O.A. Optimization of Linear Fractional Functions on Allocations. Kyiv: Naukjva Dumka, 2011. 139 p. (in Russian)
10. Sergienko I.V., Iemets O.A., Chernenko O.A. Solving the conditional optimization problem for a fractional linear objective function on a set of arrangements by the branch and bound method. Cybern Syst Anal. 2012. 48 (6). P. 832–836. https://doi.org/10.1007/s10559-012-9462-3
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Russian) | Next