SJR: 0.232 SNIP: 0.464 CiteScore™: 0.27

ISSN 打印: 1064-2315
ISSN 在线: 2163-9337

# 自动化与信息科学期刊

DOI: 10.1615/JAutomatInfScien.v51.i8.30
pages 31-42

## Method of Solving Problem of Conditional Optimization on Combinatorial Set of Arrangements

Lyudmila N. Kolechkina
University of Lodz, Lodz (Poland)
Alla N. Nagornaya
National University of "Kyiv-Mohyla Academy", Kiev
Victor V. Semenov
V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kiev

### ABSTRACT

The paper considered a formulated optimization problem on a combinatorial set of arrangements and suggested a method for its solution taking into account satisfaction of conditions imposed on gains of restrictions and objective function. The method consists of three steps. The first step constructs normalization and compliance matrices which provide transformation of arrangements set elements to a necessary form for the objective function and the given restrictions. The second step consists in finding the first support solution taking into account the arrangements set property. It is worth noting that to find the first support solution it is sufficient to calculate gains of restrictions. If the feasible solution satisfies presented inequalities, the initial data are fixed to be the verification conditions for the next improved solution. The value of objective function is determined by calculating objective function gains without the need to calculate the entire previous function. The third step provides finding the optimal solution at direct improvement of the obtained support solution. This step formulated sufficient and necessary conditions to search for the optimal solution, considered numerical examples of searching for externa of functions on the arrangements set and also presented numerical experiment for the case of |Ak3| with growing number of sample units of the arrangements set (k). It is also worth noting that the number of steps of searching for the optimal solution does not significantly increase at a sharply increased number of elements of arrangements set. Analyzing the indicator of percentage ratio of the considered points number when searching for the optimal solution and the number of elements of arrangements set it should be noted its considerable reduction that indicates to efficiency of the proposed method. So this method application allows us to find the function extremum on the set of arrangements over the finite number of steps.

### REFERENCES

1. Sergienko I.V., Shilo V.P., Discrete optimization problems: problems, methods of solution, studies [in Russian], Naukova dumka, Kiev, 2003. .

2. Zgurovskiy M.Z., Pavlov A.A., Stubborn problems of combinatorial optimization in planning and decision making [in Russian], Naukova dumka, Kiev, 2016. .

3. Colbourn C.J., DinitzJ.H., Handbook of combinatorial designs, second edition, CRC Press, Boca Raton, FL, 2010. .

4. Stoyan Yu.G., Yakovlev S.V., Mathematical models and optimization methods of geometrical design [in Russian], Naukova dumka, Kiev, 1986. .

5. Korte B., Vygen J., Combinatorial optimization: theory and algorithms, Springer, New York, 2018. .

6. Pardalos P.M., D-Z. Du, Graham R.L., Handbook of combinatorial optimization, Springer, New York, 2013. .

7. Papadimitriou C.H., SteiglitzK., Combinatorial optimization: algorithms and complexity, Dover Publications, Mineola, 2013. .

8. Sergienko I.V., Shilo V.P., Modern approaches to solving complex discrete optimization problems, A?8 Journal o/Automation and Information Sciences, 2016, 48, No. 1, 15-24. .

9. Hulianytskyi L., Riasna I., Formalization and classification of combinatorial optimization problems, Optimization Methods and Applications, Ed. by Butenko S., et al., Springer, New York, 2017, 130, 239-250. .

10. SemenovaN.V., Kolechkina L.M., Vector problems of discrete optimization on combinatorial sets: methods of studying and solving [in Ukrainian], Naukova dumka, Kiev, 2009. .

11. Semenova N.V., Kolechkina L.N., Nagornaya A.N., Solution and investigation of vector problems of combinatorial optimization on a set of permutations, Journal o/Automation and In/ormation Sciences, 2008, 40, No. 12, 67-80. .

12. Koliechkina L.N., DvirnaO.A., Nagornaya A.N. Modified coordinate method to solve multicriteria optimization problems on combinatorial configurations, Cybernetics and Systems Analysis, 2014, 59, No. 4, 620-626. .

13. Stoyan Yu.G., Emets O.O., Theory and methods of Euclidean combinatorial optimization [in Ukrainian], Institut systemnykh doslidzhen osvity, Kiev, 1993. .

14. Yakovlev S.V., The theory of convex continuations of functions on vertices of convex polygons, Computational Mathematics and Mathematical Physics, 1994, 34, No. 7, 959-965. .

15. Yakovlev S., Convex extensions in combinatorial optimization and their applications, Optimization Methods and Applications, Springer, New York, 2017, 130, 567-584. .

16. Yakovlev S.V., Valuiskaya O.A., Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints, U3rainian Mathematical Journal, 2001, 53, No. 9, 1535-1545. .

17. Pichugina O.S., Yakovlev S.V., Continuous representations and functional extensions in combinatorial optimization, Cybernetics and Systems Analysis, 2016, 52, No. 6, 921-930. .

18. Stoyan Y.G., Yakovlev S.V., ParshinO.V., Quadratic optimization on combinatorial sets in Rn, Cybernetics and Systems Analysis, 1991, 27, No. 4, 562-567. .

19. Emetz O.A., Emetz O.A., Emetz E.M., Modification of combinatorial clipping method in optimization problems on vertex located sets, Kiberneti3a i sistemnyi analiz, 2009, 45, No. 5, 129-136. .

20. Emets O.O., Kolechkina L.M., Combinatorial optimization problems with fractional-linear objective functions [in Russian], Naukova dumka, Kiev, 2005. .

21. Emetz O.O., Kolechkina L.M., Optimization problem on permutations with fractional-linear objective function: characteristics of set of feasible solutions, U3rains3yi matematychnyi zhurnal, 2000, 52, No. 12, 1630-1640. .

22. Yakovlev S.V., Pichugina O.S., Properties of combinatorial optimization problems over polyhedral-spherical sets, Cybernetics and Systems Analysis, 2018, 54, No. 1, 99-109. .

23. Pichugina O., Yakovlev S., Optimization on polyhedral-spherical sets: Theory and applications, Proceedings o/IEEE First U3raine Con/erence on Electrical and Computer Engeneering (UKRCON 2017), Kiev, 2017, 1167-1175. .

24. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V., Method of balancing rotating discretely distributed masses, Energomashinostroyenie, 1982, No. 2, 4-5. .

25. Yakovlev S.V., Grebennik I.V., Localization of solutions of some problems of nonlinear integer optimization, Cybernetics and Systems Analysis, 1993, 29, No. 5, 419-426. .

26. Semenova N.V., Kolechkina L.N., Nagirna A.N., An approach to solving discrete vector optimization problems over a combinatorial set of permutations, Cybernetics and Systems Analysis, 2008, 44, No. 3, 441-451. .

27. Semenova N.V., Kolechkina L.N., Nagornaya A.N., Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations, Journal of Automation and Information Sciences, 2008, 40, No. 12, 27-42. .

28. SemenovaN.V., Kolechkina L.N., A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements, Cybernetics and Systems Analysis, 2009, 45, No. 3, 438-445. .

29. SemenovaN.V., KolechkinaL.N., Nagornaya A.N., On approach to solving vector problems with fractionally linear functions of the criteria on the combinatorial set of arrangements, Journal of Automation and Information Sciences, 2010, 42, No. 2, 67-80. .

30. Koliechkina L.N., Dvirna O.A., Solving extremum problems with linear fractional objective functions on the combinatorial configuration of permutations under multicriteriality, Cybernetics and Systems Analysis, 2017, 53, No. 4, 590-599. .

31. Kolechkina L.M., Nagirna A.M., Combinatorial mathematical model of multicriterion optimization when constructing computer networks, Matematychni mashyny i systemy, 2016, No. 6, 26-41. .

32. Donets G.P., Kolechkina L.M., Extreme problems on combinatorial configurations [in Ukrainian], RVVPUET, Poltava, 2011. .

33. StoyanYu.G., Yakovlev S.V., Pichugina O.S., Euclidean combinatorial configurations: monograph [in Russian], Konstanta, Kharkov, 2017. .

34. Yakovlev S.V., On some classes of spatial configurations of geometric objects and their formalization, Journal of Automation and Information Sciences, 2018, 50, No. 9, 38-50. .

35. Yakovlev S.V., Formalization of spatial configuration optimization problems with a special function class, Cybernetics and Systems Analysis, 2019, 55, No. 4, 512-523. .

36. Yakovlev S., Pichugina O., YarovayaO., On optimization problems on the polyhedral-spherical configurations with their properties, Proceedings of IEEE First International Conference on System Analysis Intelligent Computing (SAIC 2018), Kiev, 2018, 94-100. .

37. Yakovlev S., Pichugina O., Yarovaya O., Polyhedral spherical configuration in discrete optimization, Journal of Automation and Information Sciences, 2019, 51, No. 1, 38-50. .

38. Nagirna A.M., SemenovV.V., Optimization of software choice based on multicriteria models on indefinitely given combinatorial set, Visnyk Kyivskogo natsionalnogo universytetu imeni Tarasa Shevchenka, Seriya fizyko-matematychni nauky, 2012, No. 2, 188-193. .