2023, випуск 2, c. 11-22
Одержано 11.07.2023; Виправлено 21.07.2023; Прийнято 25.07.2023
Надруковано 28.07.2023; Вперше Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Застосування методу глобального рівноважного пошуку для розв’язання задач булевого програмування
І.В. Сергієнко 
, В.П. Шило, В.О.
Рощин, П.В. Шило *
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Останнім часом зростає роль методів і алгоритмів розв’язання дискретних оптимізаційних задач у математичному забезпеченні комп’ютерних технологій різного рівня і призначення. У зв’язку з цим особливу увагу слід звертати на ефективність методів дискретної оптимізації, стимулюючи розвиток методів, які дають змогу розв’язувати складні прикладні задачі. Таким ефективним є представлений у роботі метод глобального рівноважного пошуку (ГРП, GES) розв’язків задач булевого програмування.
Мета роботи – опис результатів успішного застосування наближеного імовірнісного методу GES для розв’язання різних класів задач булевого програмування.
Результати. Розглянуто застосування послідовних алгоритмів GES для розв’язання задач булевого лінійного, булевого квадратичного програмування та ін. з урахуванням їхньої специфіки. Проведений порівняльний аналіз розроблених алгоритмів з кращими світовими аналогами показав ефективність алгоритмів GES. Для розпаралелювання процесу оптимізації для задач дискретного програмування створено об’єднання (портфелі і команди) алгоритмів. Досліджено ефективність роботи портфелів і команд алгоритмів GES на прикладі задачі про максимальний зважений розріз графу та проведено їхнє порівняння.
Висновки. Отриманий досвід використання алгоритмів GES та їхніх модифікацій для розв’язання різних класів задач свідчить про те, що метод GES є кращим наближеним методом булевого програмування. Об’єднання алгоритмів GES дозволяє суттєво прискорити оптимізаційний процес. Більш ефективними є команди алгоритмів.
Ключові слова: метод глобального рівноважного пошуку, задачі булевого програмування, експериментальні дослідження, ефективність алгоритмів, об’єднання (портфелі і команди) алгоритмів.
Цитувати так: Сергієнко І.В., Шило В.П., Рощин В.О., Шило П.В. Застосування методу глобального рівноважного пошуку для розв’язання задач булевого програмування. Cybernetics and Computer Technologies. 2023. 2. С. 11–22. https://doi.org/10.34229/2707-451X.23.2.2
Список літератури
1. Шило В.П. Метод глобального равновесного поиска. Кибернетика и системный анализ. 1999. Т. 35, № 1. С. 74–81. https://doi.org/10.1007/BF02667916
2. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. 472 с.
3. Kirkpatrick S., Gelatti C.D., Vecchi M.P. Optimization by simulated annealing. Science. 1983. Vol. 220. P. 671–680. https://doi.org/10.1126/science.220.4598.671
4. Aarts E., Korst J. Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. New York: J. Wiley and Sons, 1989. 284 p.
5. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Киев: Наукова думка, 2003. 264 с.
6. Сергієнко І.В., Шило В.П., Рощин В.О. Дискретна оптимізація. Алгоритми та їхнє ефективне використання. Київ: Наукова думка, 2020. 144 с.
7. Papadimitriou C., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. New York: Dover Publications, 1998. 528 p.
8. Glover F., Laguna M. Tabu search. Boston: Kluwer Academic Publishers, 1997. 382 р. https://doi.org/10.1007/978-1-4615-6089-0
9. Рощин В.О., Боярчук Д.О., Ляшко В.І., Шило П.В. Алгоритм глобального рівноважного пошуку розв’язання задачі про покриття. Наукові записки НаУКМА. Комп`ютерні науки. 2014. Т. 163. С. 25–32. https://ekmair.ukma.edu.ua/handle/123456789/3402
10. Шило В.П., Шило О.В. Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска. Кибернетика и системный анализ. 2011. Т. 47, № 6. С. 68—78. https://doi.org/10.1007/s10559-011-9368-5
11. Alidaee B., Kochenberger G., Ahmadian A. 0–1 quadratic programming approach for the optimal solution of two scheduling problems. International J. of Systems Science. 1994. Vol. 25. P. 401–408. https://doi.org/10.1080/00207729408928968
12. Gallo G., Hammer P.L., Simeone B. Quadratic knapsack problems. Math. Programming. 1980. Vol. 12. P. 132–149. https://doi.org/10.1007/BFb0120892
13. Pardalos P.M., Xue J. The maximum clique problem. J. of Global Optimiz. 1994. Vol. 4. P. 301–328. https://doi.org/10.1007/BF01098364
14. Palubeckis G. Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica. 2006. Vol. 17. No. 2. P. 279–296. https://doi.org/10.15388/Informatica.2006.138
15. Lu Z., Glover F., Hao Jin-Kao. A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 2010. Vol. 207, No. 3. P. 1254–1262. https://doi.org/10.1016/j.ejor.2010.06.039
16. Barahona F., Grotschel M., Junger M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 1988. Vol. 36. P. 493–513. https://doi.org/10.1287/opre.36.3.493
17. Chang K.C., Du D.H.-C. Efficient algorithms for layer assignment problem. IEEE Trans. on Computer – Aided Design of Integrated Circuits and Systems. 1987. Vol. 6. P. 67–78. https://doi.org/10.1109/TCAD.1987.1270247
18. Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1995. Vol. 20. P. 181–244. https://doi.org/10.1090/dimacs/020/04
19. Prokopyev O., Shylo O., Shylo V. Solving weighted MAX-SAT via global equilibrium search. Oper. Res. Lett. 2008. Vol. 36, No. 4. P. 434–438. https://doi.org/10.1016/j.orl.2007.11.007
20. Шило В.П., Шило О.В. Решение задачи о максимальном разрезе графа методом глобального равновесного поиска. Кибернетика и системный анализ. 2010. Т. 46, № 5. С. 68–79. https://doi.org/10.1007/s10559-010-9256-4
21. Шило В.П., Шило О.В., Рощин В.А. Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа. Кибернетика и системный анализ. 2012. Т. 48, № 4. С. 101–105. https://doi.org/10.1007/s10559-012-9435-6
22. Shylo V.P., Shylo O.V. Path relinking scheme for the max-cut problem within global equilibrium search. International J. of Swarm Intelligence Res. 2011. Vol. 2, N 2. P. 42–51. https://doi.org/10.4018/jsir.2011040103
23. Glover F., Laguna M., Marti R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 39. P. 653–684.
24. Helmberg C., Rendl F. A spectral bundle method for semidefinite programming. SIAM J. on Optimization. 2000. Vol. 10. P. 673–696. https://doi.org/10.1137/S1052623497328987
25. Burer S., Monteiro R.D.C., Zhang Y. Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM J. on Optimization. 2002. Vol. 12. P. 503–521. https://doi.org/10.1137/S1052623400382467
26. Шило В.П., Рощин В.А., Шило П.В. Построение портфеля алгоритмов для распараллеливания процесса решения задачи о максимальном взвешенном разрезе графа. Компьютерная математика. 2014. № 2. C. 163–170.
27. Шило В.П., Рощин В.О., Шило П.В. Паралельні алгоритми розв’язання задач булевого квадратичного програмування. Компьютерная математика. 2015. № 2. C. 12–20. http://dspace.nbuv.gov.ua/handle/123456789/168376
28. Shylo V.P., Glover F., Sergienko I.V. Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Cybernetics and Systems Analysis. 2015. Vol. 51, No. 1. P. 20–29. https://doi.org/10.1007/s10559-015-9692-2
29. Shylo V.P., Shylo O.V. Algorithm Portfolios and Teams in Parallel Optimization. Optimization Methods and Applications. S. Butenko, P.M. Pardalos, V. Shylo (eds.). New York: Springer, 2017. Vol. 130. P. 481–493. https://doi.org/10.1007/978-3-319-68640-0_23
30. Benlic U., Hao J.K. Breakout local search for the max-cut problem. J. Engineering Applications of Artificial Intelligence. 2013. Vol. 26, No. 3. P. 1162–1173. https://doi.org/10.1016/j.engappai.2012.09.001
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна