Control Systems and Computers, N6, 2020, Article 3
https://doi.org/10.15407/csc.2020.06.029
Control Systems and Computers, 2020, Issue 6 (290), pp. 29-34.
UDC 519.718
UDC 364.2:331; 681.513
L.M. Koliechkina, Doctor of Physical and mathematical sciences, Professor, University of Lodz, 22 Banahast., Lodz, 90-238, Poland, ludapl@ukr.net
A.M. Nahirna, PhD, Physical and mathematical, Associate Professor, National University of “Kyiv-Mohyla Academy”, 2 Skovorodast., Kyiv, 04070, Ukraine, naghirnaalla@ukr.net
Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the set of Placements
Introduction. An optimization problem on a combinatorial set of partial permutations with additional constraints is formulated in the paper. An algorithm for solving this type of problem is considered, which consists of four steps. The algorithm lies in constructing a graph of a set of partial permutations to find the optimal solution. An example of a practical implementation of the presented algorithm is given.
Purpose of this article is to present a method for solving the problem of conditional optimization on a graph of the set of partial permutations and to demonstrate a practical example of implementation.
Methods. The method for solving the conditional optimization problem on the combinatorial set of partial permutations.
Results. The model of the problem of conditional optimization on the set of partial permutations is formulated. The linear form of the objective function is obtained by interpreting the elements of the set of partial permutations as points of the Euclidean space. A combinatorial polytope of allocations is considered for which there is a graph of the set of partial permutations An algorithm for solving this problem is proposed and its practical applicability is demonstrated.
Conclusion. The proposed algorithm for solving the conditional optimization problem provides for the representation of the admissible of the Set of Partial Permutations in the form of a graph, which significantly reduces the search path for the optimal solution, as evidenced by the practical example considered.
Download full text! (In English)
Keywords: conditional optimization problem, optimal solution, graph, subgraph, of the Set of Partial Permutations, objective function, constraints.
- Sergienko, I.V., Shilo, V.P., 2003. Discrete Optimization Problems: Challenges, Analysis Tech-niques, and Solution, Naukova Dumka, Kyiv. 261 p. (in Russian).
- Bernhard, K., Jens, V., 2012. Combinatorial Optimization, Theory and Algorithms. Springer-Verlag, Berlin, 627 p.
- Colbourn, C.J., Dinitz, J.H., 2010. Handbook of Combinatorial Designs, Second Edition. CRC Press, 784 p.
https://doi.org/10.1201/9781003040897 - Korte, B., Vygen, J., 2018. Combinatorial Optimization: theory and algorithms. Heidelberg; New York : Springer, 698 p.
https://doi.org/10.1007/978-3-662-56039-6 - Pardalos, P.M., D-Z. Du, Graham, R.L., 2013. Handbook of combinatorial optimization. New York : Springer, 3409 p.
https://doi.org/10.1007/978-1-4419-7997-1 - Papadimitriou, C.H., Steiglitz, K., 2013. Combinatorial optimization: algorithms and complexi-ty. Mineola : Dover Publications, 528 p.
- Hulianytskyi, L., Riasna, I., 2017. “Formalization and classification of combinatorial optimiza-tion problems,” Springer Optimization and its Applications, 130, pp. 239-250.
https://doi.org/10.1007/978-3-319-68640-0_11 - Timofeeva, N.K., 2002. “Methods of Constructing Argument of Objective Function in Combina-torial Optimization Problems”. Cybernetics and Systems Analysis, 38 (6), pp. 873-878.
https://doi.org/10.1023/A:1022944021651 - Koliechkina, L.N., Nahirna, A.N., 2020. “Solutions of the Combinatorial Problem with a Quadratic Fractional Objective Function on the Set of Permutations”. Cybernetics and Systems Analysis, 56 (3), pp. 455-465.
https://doi.org/10.1007/s10559-020-00261-6 - Koliechkina, L.N., Dvirna, O.A., Nagornaya, A.N., 2014. “Modified Coordinate Method to Solve Multicriteria Optimization Problems on Combinatorial Configurations”. Cybernetics and Systems Analysis, 59 (4), pp. 620-626.
https://doi.org/10.1007/s10559-014-9650-4 - Yakovlev, S.V., Pichugina, O.S., 2018. “Properties of Combinatorial Optimization Problems Over Polyhedral-Spherical Sets”. Cybernetics and Systems Analysis, 54 (1), pp. 99-109.
https://doi.org/10.1007/s10559-018-0011-6 - Yakovlev, S., 2017. “Convex extensions in combinatorial optimization and their applications”. Springer Optimization Methods and Applications, 130, pp. 567-584.
https://doi.org/10.1007/978-3-319-68640-0_27 - Koliechkina, L.N., Dvirna, O.A., 2017. “Solving Extremum Problems with Linear Fractional Objective Functions on the Combinatorial Configuration of Permutations Under Multicriteriality”. Cybernetics and Systems Analysis, 53 (4), pp. 590-599.
https://doi.org/10.1007/s10559-017-9961-3 - Donets, G.P., Koliechkina, L.N., 2011. “Extremum Problems on Combinatorial Configurations”, RVV, Poltava, 309 p. (in Ukrainian).
- Stoyan, Y.G., Yakovlev, S.V., Pichugina, O.S., 2017. The Euclidean combinatorial configurations: a monograph. Constanta, Kharkiv, 268p.
- Yakovlev, S.V., 2019. “Formalization of spatial configuration optimization problems with a special function class”. Cybernetics and Systems Analysis, 55 (4), pp. 512-523.
https://doi.org/10.1007/s10559-019-00167-y - Semenova, N.V., Kolechkina, L.N., 2009. Vector Discrete Optimization Problems on Combinatorial Sets: Methods of Analysis and Solution, Naukova Dumka, Kyiv, 266 p. (in Ukrainian).
Received 24.11.2020
