Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous
cannonical link button


ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes

Tytuł artykułu

Optimization of linear functions on a cyclic permutation. Based on the random search

Autorzy Grebennik, I.  Baranov, O.  Chorna, A.  Gorbacheva, E. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
EN For creating adequate mathematical models of combinatorial problems of constructing optimal cyclic routes, mathematical modeling and solving a number of planning and control tasks solutions of optimization problems on the set of cyclic permutations are required. Review of the publications on combinatorial optimization demonstrates that the optimization problem on the cyclic permutations have not been studied sufficiently. This paper is devoted to solving optimization problem of a linear function with linear constraints on the set of cyclic permutations. For solving problems of this class using of known methods, taking into account the properties of a combinatorial set of cyclic permutations, is proposed. For this purpose we propose a method based on the ideology of random search. Heuristic method based on the strategy of the branch and bound algorithm is proposed to solve auxiliary optimization problem of a linear function without constraints on the set of cyclic permutations. Since application of the branch and bound algorithm immediately leads to an exponential growth of the complexity with increasing the dimension of the problem a number of modifications are suggested. Modifications allow reducing computational expenses for solving higher dimension problems. The effectiveness of the proposed improvements is demonstrated by computational experiments.
Słowa kluczowe
EN combinatorial optimization   linear function   cyclic permutations   random search   branch and bound algorithm   parallel computing  
Wydawca Polish Academy of Sciences, Branch in Lublin
Czasopismo ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes
Rocznik 2016
Tom Vol. 5, No 3
Strony 211--216
Opis fizyczny Bibliogr. 21 poz., tab., wz.
autor Grebennik, I.
autor Baranov, O.
  • Kharkiv National University of Radioelectronics
autor Chorna, A.
  • Kharkiv National University of Radioelectronics
autor Gorbacheva, E.
  • Kharkiv National University of Radioelectronics
1. Sergienko I.V. 1988 Mathematical models and methods for solving discrete optimization, K.: Naukova Dumka, 472. (In Russian).
2. Yemets O.A., Barbolina T.N. 2008 Combinatorial optimization on arrangements, K.: Naukova Dumka, 157. (In Russian).
3. I. Alekseyev, I. Khoma, N. Shpak. 2013. Modelling of an impact of investment maintenance on the condition of economic protectability of industrial enterprises. Econtechmod 2(2), Lublin ; Rzeszow, 3-8.
4. Heorhiadi, N. Iwaszczuk, R. Vilhutska. 2013. Method of morphological analysis of enterprise management organizational structure. Econtechmod 2(4), Lublin ; Rzeszow, 17-27.
5. N. Podolchak, L. Melnyk, B. Chepil. 2014. Improving administrative management costs using optimization modeling. Econtechmod 3(1), Lublin ; Rzeszow, 75–80.
6. Lobozynska S. 2014. Formation of optimal model of regulation of the banking system of Ukraine. Econtechmod 3(2), Lublin ; Rzeszow, 53-57.
7. Stoyan, Yu., Yemets, О. 1993. Theory and methods of Euclidean combinatorial optimization, ISDO, Kyiv. (In Ukrainian).
8. Stoyan Y. G., Yakovlev S. V. 1986. Mathematical models and optimization methods of geometric engineering. K.: Naukova Dumka, 268. (In Russian).
9. Yemets O.A., Barbolina T.N. 2003 Solution of linear optimization problems on arrangements by cutting Cybernetics and Systems Analysis, № 6.
10. Valuiskaya O.A., Yakovlev S.V. 1999 On the minimization of a linear function on the tops of permutation polyhedron with given linear constraints, Options. NASU number 11, pp 103-107.
11. Grebennik I. V. 1999 The solution of some problems of constrained optimization of linear functions on permutation polyhedron, Radioelectronics and Informatics, № 1, pp. 55–59.
12. Grebennik I.V., Baranov A.V. 2007 Optimization of linear functions with linear constraints on combinatorial sets on the basis of a random search, Arts. intelligence, № 1, pp. 132–137.
13. Grebennik I.V., Litvinenko A.S., Titova O.S. 2012 Optimization of a linear function on the set of cyclic permutations, Bionics Intelligence, №2(79), pp.8–12.
14. Stanley, R. 1986. Enumerative combinatorics, vol 1, Wadsworth, Inc. California.
15. Bona M. 2004 Combinatorics of permutations Chapman & Hall, CRC, 337 c.
16. Donald Knuth . 2005. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley, 144.
17. Donald L.Kreher, Douglas R.Stinson. 1999. Combinatorial Algorithms: Generation Enumeration and Search, CRC Press, 329.
18. Rekleytis G., Reyvindran A., Regsdel K. 1986 Optimization in technology, pp. 348.
19. Igor Grebennik, Olga Chorna 2015. Elements transpositions and their impact on the cyclic structure of permutations. An International Quarterly Journal on Economics of Technology and Modelling Processes . — 2015. — Vol. 4, № 3. — pp. 33–38.
20. Chernikov S.N. 1968 Linear inequalities, M .: Science, pp. 488. (In Russian).
21. Quinn M.J. 2004 Parallel Programming in C with MPI and OpenMP, New York: NY: McGraw-Hill.
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-c609f6a4-41df-459c-8e86-5282a2bcdb47