DOI: https://doi.org/10.20535/SRIT.2308-8893.2017.4.07

Оптимізація на загальній множині перестановок зі знаком

Oksana S. Pichugina

Анотація


Уведено загальну множину перестановок зі знаком і розглянуто підходи до оптимізації на ній, що ґрунтуються на зануренні в арифметичний евклідів простір. У межах дослідження вивчено властивості евклідової комбінаторної множини та її опуклої оболонки (загального багатогранника перестановок зі знаком), такі як потужність множини, незвідне H-подання багатогранника, його вимірність, критерії вершин та суміжності вершин, а також кількість комбінаторно нееквівалентних багатогранників фіксованої вимірності. Досліджено особливості поведінки кількох класів функцій на загальній множині перестановок зі знаком. Побудовано ряд функціонально-аналітичних подань цієї множини, у тому числі поліедрально-суперсферичне і строге суперсферичне. Наведено явні розв’язки лінійної задачі та задачі проектування на множину перестановок зі знаком. Проведене дослідження дозволяє застосовувати неперервні методи до оптимізації на дискретній множині й отримувати як точні, так і наближені розв’язки оптимізаційних задач з оцінкою точності.

Ключові слова


комбінаторна оптимізація; многогранно-сферична множина; перестановки зі знаком; загальна множина перестановок; бінарна множина; суперсфера; многогранно-поверхневий метод; метод умовного градієнта

Повний текст:

PDF (Русский)

Посилання


Kochenberger G. The unconstrained binary quadratic programming problem: a survey / G. Kochenberger, J.-K. Hao, F. Glover etc // Journal of Combinatorial Optimization. — 2014. — N 1. — P. 58-81. DOI: 10.1007/s10878-014-9734-0.

Pichugina O. Convex extensions and continuous functional representations in optimization, with their applications / O. Pichugina, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. — 2016. — Vol. 4(2) . — P. 129–152. DOI: 10.1166/jcsmd.2016.1103

Stojan Ju.G. Matematicheskie modeli i optimizatsionnye metody geometricheskogo proektirovanija / Ju.G. Stojan, S.V. Jakovlev. — K. : Nauk. dumka, 1986. — 268 s.

Stojan Ju.H. Teorija i metody evklidovoyi kombinatornoyi optymizatsiyi / Ju.H. Stojan, O. O. Yemets'. — K. : In-t systemn. doslidzh. osvity, 1993. — 188 s.

Stojan Ju.G. Nekotorye svojstva spetsial'nyh kombinatornyh mnozhestv (Preprint AN USSR/Institut problem mashinostr.; 85) / Ju.G. Stojan. — Har'kov, 1980. — 22 s.

Taha H. A. Integer Programming: Theory, Applications, and Computations. Edited by J. William Schmidt / H.A. Taha. — New York: Academic Press, 2014. — 392 p.

Sherali H.D. A reformulation-linearization technique for solving discrete and continuous nonconvex problems / H.D. Sherali, W.P. Adams, P.M. Pardalos (eds.).— Dordrecht: Kluwer Academic Publishers, 1999. — 518 p. DOI: 10.1007/978-1-4757-4388-3.

Pichugina O. Continuous Approaches to the Unconstrained Binary Quadratic Problems / O. Pichugina, S. Yakovlev // Mathematical and Computational Approaches in Advancing Modern Science and Engineering, Edited J. Bélair et al. — Springer, Switzerland. — 2016. — P. 689–700. DOI: 10.1007/978-3-319-30379-6_62.

Pichugina O.S. Continuous Representations and Functional Extensions in Combinatorial Optimization / O.S. Pichugina, S.V. Yakovlev // Cybernetics and Systems Analysis. — 2016. — Vol. 52, N 6. — P. 921–930. DOI: 10.1007/s10559-016-9894-2.

Pichugina O. Continuous Representation Techniques in Combinatorial Optimization / O. Pichugina, S. Yakovlev // IOSR Journal of Mathematics. — 2017. — Vol. 13, N 2, Ver.V. — P. 12–25. DOI: 10.9790/5728-1302051225.

Pichugina O. Optimization on Polyhedral-Spherical Sets: Theory and Applications / O. Pichugina, S. Yakovlev // In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON) . — 2017. — P. 1167–1174. DOI: 10.1109/UKRCOM.2017.8100436.

Jakovlev S.V. Teorija vypuklyh prodolzhenij funktsij na vershinah vypuklyh mnogogrannikov / S. V. Jakovlev // Zhurn. vychisl. matem. i matem. fiz. — 1994. — 34, № 7. — S. 1112–1119.

Jakovlev S.V. O nekotoryh klassah zadach optimizatsii na kombinatornyh mnozhestvah razmeschenij / S.V. Jakovlev, I.V. Grebennik // Izv. vuzov. Ser. Mat. — 1991. — №11. — S. 26 – 30.

Postnikov A. Permutohedra, associahedra, and beyond / A. Postnikov // IMRN: International Mathematics Research Notices. — 2009. — N 6. — P. 1026-1106. DOI: 10.1093/imrn/rnn153.

Weisstein E.W. CRC Concise Encyclopedia of Mathematics, Second Edition / E.W. Weisstein. — Boca Raton: CRC Press, 2002. — 3242 p.

Emelichev V.A. Mnogogranniki, grafy, optimizatsija (kombinatornaja teorija mnogogrannikov) / V.A. Emelichev, M.M. Kovalev, M.K. Kravtsov. — M.: Nauka. Gl. red. fiziko-mat. lit-ry, 1981. — 344 s.

Onaka S. Superspheres: intermediate shapes between spheres and polyhedra / S. Onaka // Symmetry. — 2012. — Vol.4, N 3. — P. 336–343. DOI: 10.3390/sym4030336.

Pichugina O.S. Funktsional'no-analiticheskie predstavlenija obschego perestanovochnogo mnozhestva / O.S. Pichugina, S.V. Jakovlev // Eastern-European Journal of Enterprise Technologie. — 2016. — № 1 — S. 101–126. DOI: 10.15587/1729-4061.2016.58550.

Berstein Y. Parametric nonlinear discrete optimization over well-described sets and matroid intersections / Y. Berstein, J. Lee, S. Onn, R. Weismantel // Mathematical Programming. — 2010. — Vol. 124, N 1/2 — P. 233–253. DOI: 10.1007/s10107-010-0358-6.

Bertsekas D.P. Nonlinear Programming, 2nd edn. / D.P. Bertsekas. — Belmont: Athena Scienific, 1999. — 708 p.

Huljanyts'kyj L.F. Prykladni metody kombinatornoyi optymizatsiyi : navchal'nyj posibnyk / L.F. Huljanyts'kyj, O.Ju. Mulesa. — K: Vydavnycho-polihraf. tsentr "Kyyivs'kyj universytet", 2016. — 142 s.

Sergienko I.V. Methods of optimization and systems analysis for problems of transcomputational complexity / I.V. Sergienko. — New York: Springer, 2012. — 226 p. DOI: 10.1007/978-1-4614-4211-0.


Пристатейна бібліографія ГОСТ


1. Kochenberger G. The unconstrained binary quadratic programming problem: a survey / G. Kochenberger, J.-K. Hao, F. Glover etc // Journal of Combinatorial Optimization. — 2014. — N 1. — P. 58-81. DOI: 10.1007/s10878-014-9734-0.

2. Pichugina O. Convex extensions and continuous functional representations in optimization, with their applications / O. Pichugina, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. — 2016. — Vol. 4(2) . — P. 129–152. DOI: 10.1166/jcsmd.2016.1103

3. Стоян Ю.Г. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев. — К. : Наук. думка, 1986. — 268 с.

4. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян, О. О. Ємець. — К. : Ін-т системн. дослідж. освіти, 1993. — 188 с.

5. Стоян Ю.Г. Некоторые свойства специальных комбинаторных множеств (Препринт АН УССР/Институт проблем машиностр.; 85) / Ю.Г. Стоян. — Харьков, 1980. — 22 с.

6. Taha H. A. Integer Programming: Theory, Applications, and Computations. Edited by J. William Schmidt / H.A. Taha. — New York: Academic Press, 2014. — 392 p.

7. Sherali H.D. A reformulation-linearization technique for solving discrete and continuous nonconvex problems / H.D. Sherali, W.P. Adams, P.M. Pardalos (eds.).— Dordrecht: Kluwer Academic Publishers, 1999. — 518 p. DOI: 10.1007/978-1-4757-4388-3.

8. Pichugina O. Continuous Approaches to the Unconstrained Binary Quadratic Problems / O. Pichugina, S. Yakovlev // Mathematical and Computational Approaches in Advancing Modern Science and Engineering, Edited J. Bélair et al. — Springer, Switzerland. — 2016. — P. 689–700. DOI: 10.1007/978-3-319-30379-6_62.

9. Pichugina O.S. Continuous Representations and Functional Extensions in Combinatorial Optimization / O.S. Pichugina, S.V. Yakovlev // Cybernetics and Systems Analysis. — 2016. — Vol. 52, N 6. — P. 921–930. DOI: 10.1007/s10559-016-9894-2.

10. Pichugina O. Continuous Representation Techniques in Combinatorial Optimization / O. Pichugina, S. Yakovlev // IOSR Journal of Mathematics. — 2017. — Vol. 13, N 2, Ver.V. — P. 12–25. DOI: 10.9790/5728-1302051225.

11. Pichugina O. Optimization on Polyhedral-Spherical Sets: Theory and Applications / O. Pichugina, S. Yakovlev // In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON) . — 2017. — P. 1167–1174. DOI: 10.1109/UKRCOM.2017.8100436.

12. Яковлев С.В. Теория выпуклых продолжений функций на вершинах выпуклых многогранников / С. В. Яковлев // Журн. вычисл. матем. и матем. физ. — 1994. — 34, № 7. — С. 1112–1119.

13. Яковлев С.В. О некоторых классах задач оптимизации на комбинаторных множествах размещений / С.В. Яковлев, И.В. Гребенник // Изв. вузов. Сер. Мат. — 1991. — №11. — С. 26 – 30.

14. Postnikov A. Permutohedra, associahedra, and beyond / A. Postnikov // IMRN: International Mathematics Research Notices. — 2009. — N 6. — P. 1026-1106. DOI: 10.1093/imrn/rnn153.

15. Weisstein E.W. CRC Concise Encyclopedia of Mathematics, Second Edition / E.W. Weisstein. — Boca Raton: CRC Press, 2002. — 3242 p.

16. Емеличев В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. — М.: Наука. Гл. ред. физико-мат. лит-ры, 1981. — 344 с.

17. Onaka S. Superspheres: intermediate shapes between spheres and polyhedra / S. Onaka // Symmetry. — 2012. — Vol.4, N 3. — P. 336–343. DOI: 10.3390/sym4030336.

18. Пичугина О.С. Функционально-аналитические представления общего перестановочного множества / О.С. Пичугина, С.В. Яковлев // Eastern-European Journal of Enterprise Technologie. — 2016. — № 1 — С. 101–126. DOI: 10.15587/1729-4061.2016.58550.

19. Berstein Y. Parametric nonlinear discrete optimization over well-described sets and matroid intersections / Y. Berstein, J. Lee, S. Onn, R. Weismantel // Mathematical Programming. — 2010. — Vol. 124, N 1/2 — P. 233–253. DOI: 10.1007/s10107-010-0358-6.

20. Bertsekas D.P. Nonlinear Programming, 2nd edn. / D.P. Bertsekas. — Belmont: Athena Scienific, 1999. — 708 p.

21. Гуляницький Л.Ф. Прикладні методи комбінаторної оптимізації : навчальний посібник / Л.Ф. Гуляницький, О.Ю. Мулеса. — К: Видавничо-поліграф. центр "Київський університет", 2016. — 142 с.

22. Sergienko I.V. Methods of optimization and systems analysis for problems of transcomputational complexity / I.V. Sergienko. — New York: Springer, 2012. — 226 p. DOI: 10.1007/978-1-4614-4211-0.