Randomized Load-balancing for Parallel Branch-and-bound Algorithms for Multi-level Network Design
Resumo
This paper is concerned with parallel implementations of the classical branch-and-bound algorithm for a multi-level network optimization problem. Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, or electric power systems. A new model for multi-level network design is introduced and formulated as a mixed-integer program. The formulation is innovative because it integrates in the same model aspects of discrete facility location topological network design, and dimensioning. We propose implementations which are suitable for MIMD (multiple instruction stream, multiple data stream) parallel computation systems. Thus, the implementations are very convenient for use in networks of workstations which nowadays has become so popular. We have tested two versions of the branch-and-bound algorithm as well as different load balancing strategies. The results are very encouraging indicating a gain over sequential computations in terms of execution time.
Palavras-chave:
Parallel branch-and-bound, parallel computing, load balancing, network optimization, network design problems
Referências
A. Balakrishnan, T. L. Magnanti, and P. Mirchandani. A dual-based algorithm for multi-level network design. Management Science, 40(7):567–581, 1994.
F. R. B. Cruz, J. MacGregor Smith, and G. R. Mateus. Solving to optimality the uncapacitated fixed-charge network flow problem. Computers & Operations Research, 25(1):67–81, 1998.
F. R. B. Cruz, J. MacGregor Smith, and G. R. Mateus. Algorithms for a multi-level network optimization problem. European Journal of Operational Research, 118(1):165–181, 1999.
J. R. Current, C. S. ReVelle, and J. L. Cohon. The hierarchical network design problem. European Journal of Operational Research, 27:57–66, 1986.
C. W. Duin and A. Volgenant. Reducing the hierarchical network design problem. European Journal of Operational Research, 39:332–344, 1989.
D. Erlenkotter. A dual-based procedure for uncapacitated facility location. Operations Research, 26(6):992–1009, 1978.
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sundaram. PVM: Parallel Virtual Machine – A User's Guide and Tutorial for Networked Parallel Computing. MIT Press, Cambridge, Massachusetts, 1994.
B. Gendron and T. G. Crainic. Parallel branch-and-bound algorithms: Survey and synthesis. Operations Research, 42(6):1042–1066, 1994.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
R. M. Karp and Y. Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, 40(3):765–789, 1993.
P. S. Laursen. Simple approaches to parallel branch-and-bound. Parallel Computing, 19:143–152, 1993.
P. S. Laursen. Can parallel branch-and-bound without communication be effective? SIAM Journal on Optimization, 4(2):143–152, 1994.
H. P. L. Luna, N. Ziviani, and R. M. B. Cabral. The telephonic switching centre network problem: Formalization and computational experience. Discrete Applied Mathematics, 18:199–210, 1987.
G. R. Mateus, F. R. B. Cruz, and H. P. L. Luna. An algorithm for hierarchical network design. Location Science, 2(3):149–164, 1994.
G. R. Mateus, C. I. P. S. Pádua, and H. P. L. Luna. Integrated network models for local access network design. In Proceedings of the International Telecommunications Symposium, pages 6–10, Acapulco, Mexico, 1996.
M. J. Quinn. Designing Efficient Algorithms for Parallel Computers. McGraw-Hill Book Company, New York, first edition, 1987.
A. S. Tanenbaum. Computer Networks. Prentice-Hall, New York, 1981.
A. I. Tavares, M. L. B. Carvalho, and G. R. Mateus. Aided design and analysis of distributed branch-and-bound algorithms. In Annals of XV International Conference of the Chilean Society of Computer Science, pages 448–458, Arica, Chile, 1995. Chilean Society of Computer Science.
F. R. B. Cruz, J. MacGregor Smith, and G. R. Mateus. Solving to optimality the uncapacitated fixed-charge network flow problem. Computers & Operations Research, 25(1):67–81, 1998.
F. R. B. Cruz, J. MacGregor Smith, and G. R. Mateus. Algorithms for a multi-level network optimization problem. European Journal of Operational Research, 118(1):165–181, 1999.
J. R. Current, C. S. ReVelle, and J. L. Cohon. The hierarchical network design problem. European Journal of Operational Research, 27:57–66, 1986.
C. W. Duin and A. Volgenant. Reducing the hierarchical network design problem. European Journal of Operational Research, 39:332–344, 1989.
D. Erlenkotter. A dual-based procedure for uncapacitated facility location. Operations Research, 26(6):992–1009, 1978.
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sundaram. PVM: Parallel Virtual Machine – A User's Guide and Tutorial for Networked Parallel Computing. MIT Press, Cambridge, Massachusetts, 1994.
B. Gendron and T. G. Crainic. Parallel branch-and-bound algorithms: Survey and synthesis. Operations Research, 42(6):1042–1066, 1994.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
R. M. Karp and Y. Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, 40(3):765–789, 1993.
P. S. Laursen. Simple approaches to parallel branch-and-bound. Parallel Computing, 19:143–152, 1993.
P. S. Laursen. Can parallel branch-and-bound without communication be effective? SIAM Journal on Optimization, 4(2):143–152, 1994.
H. P. L. Luna, N. Ziviani, and R. M. B. Cabral. The telephonic switching centre network problem: Formalization and computational experience. Discrete Applied Mathematics, 18:199–210, 1987.
G. R. Mateus, F. R. B. Cruz, and H. P. L. Luna. An algorithm for hierarchical network design. Location Science, 2(3):149–164, 1994.
G. R. Mateus, C. I. P. S. Pádua, and H. P. L. Luna. Integrated network models for local access network design. In Proceedings of the International Telecommunications Symposium, pages 6–10, Acapulco, Mexico, 1996.
M. J. Quinn. Designing Efficient Algorithms for Parallel Computers. McGraw-Hill Book Company, New York, first edition, 1987.
A. S. Tanenbaum. Computer Networks. Prentice-Hall, New York, 1981.
A. I. Tavares, M. L. B. Carvalho, and G. R. Mateus. Aided design and analysis of distributed branch-and-bound algorithms. In Annals of XV International Conference of the Chilean Society of Computer Science, pages 448–458, Arica, Chile, 1995. Chilean Society of Computer Science.
Publicado
24/10/2000
Como Citar
CRUZ, F. R. B.; MATEUS, G. R.; SMITH, J. MacGregor.
Randomized Load-balancing for Parallel Branch-and-bound Algorithms for Multi-level Network Design. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 83-90.
DOI: https://doi.org/10.5753/sbac-pad.2000.41207.
