Parallel Branch-and-Bound: Design and Performance Understanding

• Wagner Meira Jr. University of Rochester
• Annibal Sodero UFMG
• Andréa Tavares UFMG
• Márcio Carvalho UFMG

DOI: https://doi.org/10.5753/sbac-pad.1996.19820

Resumo

Técnicas de Branch-and-Bound têm sido usadas com sucesso para a solução de problemas de otimização combinatória. Essas técnicas podem se tornar ainda mais eficientes quando paralelizadas. A paralelização da computação associada a técnicas Branch-and-Bound, entretanto, não é trivial e programadores podem ter dificuldades tanto em termos de correção quanto eficiência das paralelizações resultantes. Neste trabalho apresentamos um ambiente que auxilia programadores no desenvolvimento de aplicações paralelas de Branch-and-Bound que sejam eficientes. Esse ambiente integra duas ferramentas: (1) Sabor, que auxilia no desenvolvimento daquelas aplicações e (2) Carnival, uma ferramenta de análise e medição de desempenho que provê ao programador recursos para o entendimento do desempenho daquelas aplicações. Também apresentamos a interface da Carnival e ilustramos sua utilidade e funcionalidade através da identificação e análise das fontes de degradação de desempenho em aplicações.

Referências

R. M. Karp and Y. Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the Association for Computing Machinery, 40(3):765-789, July 1993.

T. Lai and S. Sahni. Anomalies in parallel branch-and-bound algorithms. Cm munications of the ACM, 27(6):594-602, June 1984.

P. S. Laursen. Simple approaches to parallel branch and bound. Parallel Computing, 19:143-152, 1993.

E. L. Lawler and D. E. Wood. Branch-and-bound methods: a survey. Operations Research, 14:699-719, 1966.

J. D. C. Little, K. G. Murty, D. W. Sweeney, and C. Karel. An algorithm to the traveling salesman problem. Operations Research, 11 (6):972989, November December 1963.

G. P. McKeown, V. J. Rayward-Smith, and S. A. Rush. Advances in Parallel Algorithms, chapter 5 Parallel Branch-and-bound, pages 111-150. John Willey and Sons, Inc., 1992.

W. MeiraJr., T. LeBlanc, andA. Poulos. Waiting time analysis and performance visualization in carnival. In Proc. of SIGMETRICS Symposium on Parallel and Distributed Tools, Philadelphia,PA, May 1996. ACM.

A. I. Tavares. Um sistema para implementação e análise de técnicas de branch-and-bound em redes de estações de trabalho. Master's thesis, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil, Fevereiro 1995.