Abonnement à la biblothèque: Guest
Journal of Automation and Information Sciences

Publication de 12  numéros par an

ISSN Imprimer: 1064-2315

ISSN En ligne: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Conditional Optimization of a Problem with Quadratic Objective Function on a Set of Permutations

Volume 52, Numéro 4, 2020, pp. 47-64
DOI: 10.1615/JAutomatInfScien.v52.i4.50
Get accessGet access

RÉSUMÉ

The statement of the optimization problem with the quadratic objective function on the combinatorial set of permutations is formulated. A new method of solving the optimization problem, taking into account the fulfillment of the conditions of the problems formed when considering transpositions of elements of the set of permutations is proposed. The presented method consists of three steps. At the first step, a decision tree is constructed, the branching branches of which are transpositions of the corresponding elements of the set of permutations. At this step, all possible transpositions are compiled in the quantity p that determine the further representation of the set of permutation points in the form of a permutation of the corresponding elements. Subgraphs of the graph G. are constructed from these points and subsets of the set of transpositions are compiled. It should be noted that the graph G is only a part of the polyhedron of permutations M(Pkn). In the second step, the problems are compiled whose objective functions are quadratic and are presented taking into account the transpositions under consideration. When solving each problem, a set of transpositions of elements is formed, which consists of Sqop − the subset of points in the graph G subgraph that satisfy the constraints; Sqcon − the subset of points in a subgraph of the graph G that do not satisfy the constraint; Sqcl − the subset of the cut-off points of the subgraph of the graph G that do not belong to the two previous subsets. On each subgraph of the graph G , additional constraints (4) of the problem (3)-(5) are checked. In this case, only the increments of the constraints and objective function are calculated using the necessary formulas. The set of reference solutions will consist of the point xextr at which extr F(xextr) and set of the permutation points Sac , which have not been considered during the transposition of elements, but belong to the polyhedron of the permutations M(Pkn). In the third step, the search for the optimal solution to the problem is carried out by comparing the increments of the quadratic objective function of the point xextr and points of the set Sac. The article gives a numerical example of the implementation of this method. From 120 points of the set of permutations, the optimal solution was found in 18 steps when considering 27 points and 28 cut-off points. Using this method, one can get the optimal solution in a finite number of steps.

RÉFÉRENCES
  1. Sergienko I.V., Shilo V.P., Modern approaches to solving complex discrete optimization problems, Journal of Automation and Information Sciences, 2016, 48, No. 1, 15-24.

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

  3. Colbourn C.J., Dinitz J.H., Handbook of combinatorial designs, second edition, CRC Press, London; New York, 2010.

  4. Yakovlev S.V., Gil N.I., Komyak V.M., Aristov I.V., Elements of the theory of geometric design, Ed. by V.L. Rvachev [in Russian], Naukova dumka, Kiev, 1995.

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

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

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

  8. Hulianytskyi L., Riasna I., Formalization and classification of combinatorial optimization problems, Optimization Methods and Applications, Butenko S. et al.(eds.), Springer, New York, 2017, 239-250.

  9. Semenova N.V., Kolechkina L.M., Vector problems of discrete optimization on combinatorial sets: research methods and solutions [in Ukrainian], Naukova dumka, Kiev, 2009.

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

  11. Kolechkina L.N., Dvirna O.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.

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

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

  14. Koliechkina L., Pichugina O., A horizontal method of localizing values of a linear function in permutation-based optimization, In Le Thi H.A., Le H.M., Pham Dinh T. (eds.), Optimization of Complex Systems: theory, models, algorithms and applications, Springer, London, 2020, 355-364.

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

  16. Pichugina O., Yakovlev S., Optimization on polyhedral-spherical sets: theory and applications, In 2017 IEEE First Ukrainian Conference on Electrical and Computer Engeneering (UKRCON 2017), Proceedings, Kyiv, 2017, 1167-1175.

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

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

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

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

  21. Semenova N.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.

  22. Semenova N.V., Kolechkina L.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.

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

  24. Kolechkina L.M., Nagirna A.M., Combinatorial mathematical model of multicriteria optimization in the construction of computer networks, Matematicheskiye mashiny i sistemy, 2016, No. 6, 26-41.

  25. Donets G.P., Kolechkina L.M., Extreme problems on combinatorial configurations [in Ukrainian], RVV PUET, Poltava, 2011.

  26. Kolechkina L.N., Nagornaya A.N., Semenov V.V., Method of solving problem of conditional optimization on combinatorial set of arrangements, Mezhdunarodnyi nauchno-tekhnicheskiy zhurnal "Problemy upravleniya i informatiki", 2019, No. 4, 62-72.

  27. Stoyan Yu.G., Yakovlev S.V., Pichugina O.S., Euclidean combinatorial configurations: a monograph [in Russian], Konstanta, Kharkov, 2017.

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

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

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

  31. Yemelichev V.A., Kovalev V.A., Kravtsov M.K., Polytopes, graphs and optimization, Cambridge University Press, Cambridge, 1984.

Portail numérique Bibliothèque numérique eBooks Revues Références et comptes rendus Collections Prix et politiques d'abonnement Begell House Contactez-nous Language English 中文 Русский Português German French Spain