Comparison of Parallel Implementations of the Branch-and-Bound Method for Shared Memory Systems

A. Yu. Gorchakov; Горчаков А. Ю.; M. A. Posypkin; Посыпкин М. А.

doi:10.31857/S0002338823020099

Comparison of Parallel Implementations of the Branch-and-Bound Method for Shared Memory Systems

Authors: Gorchakov A.Y.¹, Posypkin M.A.¹
Affiliations:
1. Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, 119333, Moscow, Russia
Issue: No 2 (2023)
Pages: 108-122
Section: MANAGEMENT IN STOCHASTIC SYSTEMS AND UNDER CONDITIONS OF UNCERTAINTY
URL: https://vietnamjournal.ru/0002-3388/article/view/676502
DOI: https://doi.org/10.31857/S0002338823020099
EDN: https://elibrary.ru/JDULMW
ID: 676502

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription or Fee 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).