2022, випуск 4, c. 56-81
Одержано 13.12.2022; Виправлено 18.12.2022; Прийнято 20.12.2022
Надруковано 29.12.2022; Вперше Online 28.02.2023
https://doi.org/10.34229/2707-451X.22.4.5
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Використання NEOS-сервера для розв’язання двох класів оптимізаційних задач
Г.Д. Біла 1,
О.О. Корчинський 2, П.І. Стецюк 1 * 
, О.М. Хом’як 1 , С.Б. Шеховцов 3
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
2 Ужгородський національний університет, Україна
3 Харківський національний університет радіоелектроніки, Україна
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
NEOS-cервер надає безкоштовний доступ до бібліотеки необхідного програмного забезпечення для розв’язання оптимізаційних задач. Розроблені ефективні чисельні методи можуть бути використані для конкретного застосування або для вирішення широкого кола задач математичного програмування.
Стаття присвячена дослідженню можливостей розв’язання задач оптимізації за допомогою NEOS сервера на прикладі двох задач математичного програмування: задачі лінійного булевого програмування для відомої задачі m-комівояжерів та задачі нелінійного програмування для спеціальної багатоекст-ремальної задачі на многовиді Штіфеля.
Матеріал роботи викладений у 4 розділах. У розділі 1 описано загальні відомості про використання NEOS сервера для вирішення задач оптимізації та приділено основну увагу мові математичного програмування AMPL як його складовій частині. Проведено порівняння частоти використання AMPL, GAMS та інших форматів вхідних даних, які доступні на сервері.
У другому розділі описано принцип розв’язання задач оптимізації за допомогою NEOS та наведено список наявних на сервері солверів, що підтримують AMPL. Наведено статистику частоти використання солверів CPLEX, Gurobi та BARON у порівнянні з іншими доступними на сервері солверами, а також загальну статистику кількості розв’язаних задач на сервері за 2021 рік.
У розділі 3 описано задачі лінійного булевого програмування для задачі m-комівояжерів, яка при m=1 рівносильна відомій задачі комівояжера. Наведено показники ефективності розв’язання цих задач за допомогою солверів CPLEX та Gurobi.
У розділі 4 проведено дослідження задачі нелінійного програмування для спеціальної багатоекстремальної задачі на многовиді Штіфеля. Наведено загальне формулювання задачі та формулювання її часткових випадків у залежності від обмежень, накладених на компоненти векторів. Досліджено ефективність розв’язання за допомогою солвера BARON тестових прикладів залежно від кількості векторів та їх розмірності.
Ключові слова: оптимізація, NEOS сервер, AMPL, NEOS солвери, задача комівояжера, многовид Штіфеля.
Цитувати так: Біла Г.Д., Корчинський О.О., Стецюк П.І., Хом’як О.М., Шеховцов С.Б. Використання NEOS-сервера для розв’язання двох класів оптимізаційних задач. Cybernetics and Computer Technologies. 2022. 4. С. 56–81. https://doi.org/10.34229/2707-451X.22.4.5
Список літератури
1. NEOS Solver. https://neos-server.org/ (звернення: 15.12.2022)
2. Dolan E. The NEOS Server 4.0 Administrative Guide, 2001. 41 p.
3. Moré J.J., Czyzyk J.J., Mesnier M.P. The Network-Enabled Optimization System (NEOS) Server. 1998. 13 p.
4. Gropp W., Moré J.J. Optimization Environments and the NEOS Server. 1997. 18 p.
5. Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.
6. CPLEX Optimizer. High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming. https://www.ibm.com/analytics/cplex-optimizer (звернення: 15.12.2022)
7. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/ (звернення: 15.12.2022)
8. Tawarmalani M., Sahinidis N.V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005. 103 (2). P. 225–249.
9. Sahinidis N.V. BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs. User's manual. 2021.
10. Kilinc M., Sahinidis N.V. Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems in BARON. Optimization Methods and Software. 2018. 33. P. 540–562.
11. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of travelling salesman problem. J. ACM. 1960. 3. P. 326–329.
12. Гамецкий А.Ф., Соломон Д.И. Исследование операций. Том II. Кишинэу, Эврика, 2008. 592 с.
13. Алексеева Е.В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2012. 131 с.
14. Стецюк П.И., Нуриев У.Г., Нуриева Ф.У. Новая модель целочисленного линейного программирования для задачи коммивояжера. Матеріали 7-ї Міжнародної наукової конференції "Математичне моделювання, оптимізація та інформаційні технології (MMOTI-2021)", 15–19 листопада 2021 р. С. 319–325.
15. Стецюк П.І., Соломон Д.І., Григорак М.Ю. Задачі про найкоротші k-вершинні цикли та шляхи. Кібернетика та комп'ютерні технології. 2021. № 3. С. 15–33. https://doi.org/10.34229/2707-451X.21.3.2
16. TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (звернення: 15.12.2022)
17. Balogh J., Csendes T., Rapcsák T. Some Global Optimization Problems on Stiefel Manifold. Journal of Global Optimization. 2004. 30. P. 91–101.
18. Шор Н.З., Стецюк П.И., Березовский О.А. Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля. Теория оптимальных решений. Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины. 2004. С. 3–10. http://dspace.nbuv.gov.ua/handle/123456789/84870
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна