Abo Bibliothek: Guest
Journal of Automation and Information Sciences

Erscheint 12 Ausgaben pro Jahr

ISSN Druckformat: 1064-2315

ISSN Online: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Mehr
Kauf $40.00(open in a new tab) Abonnement prüfen MARC-Eintrag herunterladen(open in a new tab) Berechtigungen erhalten(open in a new tab)

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

Volumen 51, Ausgabe 8, 2019, pp. 31-42
DOI: 10.1615/JAutomatInfScien.v51.i8.30
Get accessGet access
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

ABSTRAKT

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.

SCHLÜSSELWÖRTER: conditional optimization problem, combinatorial set of arrangements, function extremum, normalization matrix
REFERENZEN

  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. .

REFERENZIERT VON

  1. Koliechkina L., Nahirna A., Solutions of the Combinatorial Problem with a Quadratic Fractional Objective Function on the Set of Permutations, Cybernetics and Systems Analysis, 56, 3, 2020. Crossref

  2. Koliechkina L. N., Dvirna O. A., Khovben S. V., A Two-Step Method for Solving Vector Optimization Problems on Permutation Configuration, Cybernetics and Systems Analysis, 57, 3, 2021. Crossref

  3. Pichugina Oksana, Koliechkina Liudmyla, Chilikina Tatyana, Multicriteria Combinatorial Optimization Model of an Infocommunication System, 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S&T), 2021. Crossref

778 Artikelansichten 6 Artikel-Downloads Metriken
778 ANSICHTEN 6 HERUNTERLADEN 3 Crossref ZITATE Google
Scholar ZITATE

Artikel mit ähnlichem Inhalt:

Solving of Some Problems of Combinatorial Optimization on Arrangements and Permutations of Game Type Journal of Automation and Information Sciences, Vol.38, 2006, issue 5
Natalya Yu. Ustian, Oleg A. Emets
ACO-H Metaheuristic Combinatorial Optimization Method Journal of Automation and Information Sciences, Vol.42, 2010, issue 7
Sergey I. Sirenko, Leonid F. Hulyanytskyi
Studies of Problems of Combinatorial Optimization of Game Type on Arrangements Journal of Automation and Information Sciences, Vol.39, 2007, issue 1
Natalya Yu. Ustian, Oleg A. Emets
Conditional Optimization of a Problem with Quadratic Objective Function on a Set of Permutations Journal of Automation and Information Sciences, Vol.52, 2020, issue 4
Alla N. Nahirna , Lyudmila N. Kolechkina
Search for the Global Minimum of a Nondifferentiable Function by the Method of Optimal Set Partitioning Journal of Automation and Information Sciences, Vol.34, 2002, issue 3
Elena M. Kiseleva, Tatyana F. Stepanchuk

Neueste Ausgabe

Modeling of Configurations Formed when Using Microneedle Systems Gennadiy V. Sandrakov , Sergey I. Lyashko, Elena S. Bondar , Nataliya I. Lyashko , Vladimir V. Semenov Properties of Large Deviations of Empirical Estimates in a Stochastic Optimization Problem for a Homogeneous Random Field Pavel S. Knopov, Evgeniya J. Kasitskaya The Dynamics of One Arms Race Mathematical Model with a Delay Andrey V. Shatyrko, Denis Ya. Khusainov, Bedrik Puzha , Veronika Novotna Some Ways to Modeling Input Data for Information Search in the Library of Standards when Solving Semantics Problems Nadezhda K. Tymofijeva Method for Constructing Primitive Polynomials for Cryptographic Subsystems of Dependable Automated Systems Gennadiy N. Gulak Complete Asymptotics of Approximations by Certain Singular Integrals in Mathematical Modeling Konstantin N. Zhyhallo Index, Volume 52, 2020
Digitales Portal Digitale Bibliothek eBooks Zeitschriften Referenzen und Berichte Forschungssammlungen Preise und Aborichtlinien Begell House Kontakt Language English 中文 Русский Português German French Spain