Experience of multilevel parallelizing of the branch and bound method in discrete optimization problems / Popov L.D. // Automation and Remote Control. - 2007. - V. 68, l. 5. - P. 901-911.

ISSN:

00051179

Type:

Article

Abstract:

Various schemes are considered of the parallel implementation of the branch and bound method, as applied to multiprocessor computing systems (clusters) with the distributed memory. In the language of informal automata, questions are set out of the organization of the exchange of data and signals within the cluster, which afford the asynchronous operation of its processors. Common ideas are illustrated by the example of the classical traveling salesman problem and data of numerical experiments performed on the multiprocessor computing system-100 (MCS-100) are given. © Nauka/Interperiodica 2007.

Author keywords:

Index keywords:

Automata theory; Branch and bound method; Multiprocessing systems; Traveling salesman problem; Distributed memory; Multilevel parallelizing; Parallel implementation; Parallel algorithms

DOI:

10.1134/S0005117907050153

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-34249870594&doi=10.1134%2fS0005117907050153&partnerID=40&md5=c451800e1a70a9932ef2427088a64ad7

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-34249870594&doi=10.1134%2fS0005117907050153&partnerID=40&md5=c451800e1a70a9932ef2427088a64ad7
Affiliations	Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, Russian Federation
References	Korbut, A.A., Finkel'shtein, Y.Y., (1969) Diskretnoe programmirovanie (Discrete Programming), , Moscow: Nauka; Emelichev, V.A., Kovalev, M.M., Kravtsov, M.K., (1981) Mnogogranniki, grafy, optimizatsiya (Polyhedrons, Graphs, and Optimization), , Moscow: Nauka; Sergienko, I.V., (1988) Matematicheskie modeli i metody resheniya zadach diskretnoi optimizatsii (Mathematical Models and Methods of Solution of Discrete Optimization Problems), , Kiev: Naukova Dumka; Ananth, G.Y., Kumar, V., Pardalos, P., Parallel Processing of Discrete Optimization Problems (1993) Encyclopedia Microcomput, 13, pp. 129-147; Gendron, B., Grainic, T.G., Parallel Branch-And-Bound Survey and Synthesis (1994) Oper. Res, 42 (2), pp. 1042-1066; Verkhoturov, V.R., Veselovskii, V.E., Zlotov, A.V., (2000) Kombinatornye metody i algoritmy resheniya zadach diskretnoi optimizatsii bol'shoi razmernosti (Combinatorial Methods and Algorithms of Solution of Discrete Optimization Problems of Large Dimensions), , Moscow: Nauka; Voevodin, V.V., Parallel'nye vychisleniya (Parallel Computations), St. Petersburg: BKhV-Peterburg, 2004; Chetverushkin, B.N., Highly Productive Multiprocessor Computing Systems (2002) Vest. Ross. Akad. Nauk, 72 (9), pp. 786-794; Prisypkin, M.A., Sigal, I.K., Galim'yanova, N.N., (2006) Parallel'nye algoritmy v zadachakh diskretnoi optimizatsii: Vychislitel'nye modeli, biblioteki, rezul'taty eksperimentov (Parallel Algorithms in Discrete Optimization Problems: Computational Models, Library, Results of Experiments), , Moscow: Vychisl. Tsentr Akad. Nauk SSSR; Popov, L.D., On Parallel Implementation of the Branch and Bound Method for the Traveling Salesman Problem (1998) Algorithms and Software of Parallel Computations, (2), pp. 236-255. , Ekaterinburg: Ross. Akad. Nauk; Trienekes, H.W.J.M., Parallel Branch and Bound on an MIMD System, , Rotterdam: Econometric Institute, Erasmus University, Report 8640/A; Little, J., Murty, K., Sweeney, D., Karel, C., An Algorithm for Traveling Salesman Problem (1963) Oper. Res, 11 (6), pp. 972-990; (1985) The Travelling Salesman Problem, , Lawler, E.L, Lenstra, J.K, Rinnooy Kan, A.N, and Shmoys, D.B, Eds, New York: Wiley
Correspondence Address	Popov, L.D.; Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, Russian Federation
Language of Original Document	English
Abbreviated Source Title	Autom. Remote Control
Source	Scopus