Email this article Comparison of Parallel Implementations of the Branch-and-Bound Method for Shared Memory Systems
- Authors: Gorchakov A.Y.1, Posypkin M.A.1
-
Affiliations:
- Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
- Issue: No 2 (2023)
- Pages: 108-122
- Section: УПРАВЛЕНИЕ В СТОХАСТИЧЕСКИХ СИСТЕМАХ И В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
- URL: https://journals.rcsi.science/0002-3388/article/view/136869
- DOI: https://doi.org/10.31857/S0002338823020099
- EDN: https://elibrary.ru/JDULMW
- ID: 136869
Cite item
Open Access
Access granted
Subscription Access
Abstract
Four parallel algorithms are considered that implement the branch-and-bound method (BnB) for solving problems of finding a global minimum. The algorithms are designed for computing systems with shared memory. The BnB is based on two basic operations: branching and eliminating. To implement the elimination operation, interval arithmetic is used, which for real intervals defines operations similar to ordinary arithmetic. The main difference between the algorithms lies in the different implementation of storing the list of subproblems. In the process of testing on a representative set of test problems, the speed of the algorithms, their scalability, and their resistance to search anomalies are investigated.
About the authors
A. Yu. Gorchakov
Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
Email: agorchakov@frccsc.ru
Россия, Москва
M. A. Posypkin
Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
Author for correspondence.
Email: mposypkin@frccsc.ru
Россия, Москва
References
- Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // ЖВМ и МФ. 1971. Т. 11. № 6. С. 1390–1403.
- Lawler E.L., Wood D.E. Branch-and-Bound Methods: A survey // Operations research. 1966. V. 14. № 4. P. 699–719.
- Евтушенко Ю.Г., Посыпкин М.А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // ЖВМ и МФ. 2011. Т. 51. № 8. С. 1376–1389.
- Karnopp D.C. Random Search Techniques for Optimization Problems // Automatica. 1963. V. 1. № 2–3. P. 111–121.
- Solis F.J., Wets R.J.B. Minimization by Random Search Techniques // Mathematics of Operations Research. 1981. V. 6. № 1. P. 19–30.
- Marte R., Lozano J.A., Mendiburu A. et al. Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2018. P. 155–175.
- Marte R., Aceves R., LeГin M.T at al. Intelligent Multi-start Methods // Handbook of Heuristics. Cham: Springer, 2019. P. 221–243.
- Амирханова Г.А., Горчаков А.Ю., Дуйсенбаева А.Ж., Посыпкин М.А. Метод мультистарта с детерминированным механизмом рестарта // Вестн. С.-Петербургского ун-та. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. № 2. С. 100–111.
- Зайцев А.А., Курейчик В.В., Полупанов А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта // Изв. Южного федерального ун-та. Технические науки. 2010. Т 113. № 12. С. 7–12.
- Crainic T.G., Le Cun B., Roucairol C. Parallel Branch-and-bound Algorithms // Parallel Combinatorial Optimization. New Jersey: John Wiley & Sons, Inc., 2006. P. 1–28.
- Casado L.G., Martinez J.A., García I. et al. Branch-and-bound Interval Global Optimization on Shared Memory Multiprocessors // Optimization Methods & Software. 2008. V. 23. № 5. P. 689–701.
- Posypkin M., Usov A. Implementation and Verification of Global Optimization Benchmark Problems // Open Engineering. 2017. V 7. № 1. P. 470–478.
- Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems // Econometrica. 1960. V. 28. № 3. C. 497–520.
- Van Der Pas R., Stotzer E., Terboven C. Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD. London: MIT Press, 2017.
- Rabinovich S.G., Rabinovich M. Evaluating Measurement Accuracy. N.Y.: Springer, 2010.
- Dekking F.M., Kraaikamp C., Lopuhaí H.P. et al. A Modern Introduction to Probability and Statistics: Understanding why and how. London: Springer, 2005.
- Efron B., Tibshirani R. J. A An Introduction to the Bootstrap. Boca Raton: CRC press, 1994.
- Helwig N.E. Bootstrap Confidence Intervals // Twin:University of Minnesota, 2017.
- Virtanen P.,Gommers R., Oliphant T.E. et al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python // Nature methods. 2020. V. 17. № 3. C. 261–272.
- Положение о ЦКП “Информатика”. 2020. URL: http://www.frccsc.ru/ ckp (onlineНѕ accessed: 2020-07-23).
Supplementary files
