article

Distributed versus Centralized Storage and Control forParallel Branch and Bound: Mixed Integer Programming on the CM-5

Author:

Jonathan EcksteinAuthors Info & Claims

Computational Optimization and Applications, Volume 7, Issue 2

Pages 199 - 220

https://doi.org/10.1023/A:1008699010646

Published: 01 March 1997 Publication History

Abstract

This paper describes parallel, non-shared-memory implementation of the classical general mixed integer branch and bound algorithm, with experiments on the CM-5 family of parallel processors. The main issue in such an implementation is whether task scheduling and certain data-storage functions should be handled by a single processor, or spread among multiple processors. The centralized approach risks creating processing bottlenecks, while the more decentralized implementations differ more from the fundamental serial algorithm. Extensive computational tests on standard MIPLIB problems compare centralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-based global load balancing, along with a distributed “control by token” technique. Further experiments compare centralized and distributed schemes for storing heuristic “pseudo-cost” branching data. The distributed storage method is based on continual asynchronous reduction along a tree of redundant storage sites. On average, decentralized task scheduling appears at least as effective as central control, but pseudo-cost storage should be kept as centralized as possible.

References

[1]

1. E.M.L. Beale, "Branch and bound methods for mathematical programming systems," in Discrete Optimization II, Annals of Discrete Mathematics, P.L. Hammer, E.L. Johnson, and B.H. Korte (Eds.), vol. 5, pp. 201-219, 1979.

[2]

2. R.E. Bixby, E.A. Boyd, and R.R. Indovina, "MIPLIB: A test set of real-world mixed-integer programming problems," SIAM News, vol. 25, p. 16, 1992.

[3]

3. G.E. Blelloch, Vector Models for Data-Parallel Computing, MIT Press: Cambridge, MA, 1990.

Digital Library

[4]

4. S.P. Bradley, A.C. Hax, and T.L. Magnanti, Applied Mathematical Programming, Addison-Wesley: Reading, MA, 1977.

[5]

5. D.P. Christman, Programming the Connection Machine, Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1983.

[6]

6. CPLEX Optimization Inc., Using the CPLEX<sup>TM</sup> Callable Library and CPLEX<sup>TM</sup> Mixed Integer Library, Incline Village, NV, 1994.

[7]

7. S. Dowaji and C. Roucairol, "Influence of priority on tasks on load balancing strategies for distributed branch-and-bound algorithms," in Proc. Workshop on Solving Irregular Problems on Distributed-Memory Machines--9th Int. Parallel Processing Symp., Santa Barbara, CA, 1995, pp. 83-90.

[8]

8. J. Eckstein, "Parallel branch-and-bound for mixed integer programming," SIAM News, vol. 27, pp. 1, 12-15, 1994.

[9]

9. J. Eckstein, "Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5," SIAM J. Optim., vol. 4, pp. 794-814, 1994.

[10]

10. J. Eckstein, "Control strategies for parallel mixed integer branch and bound," in Proc. Supercomputing'94, Washington, DC, 1994, pp. 41-48.

Digital Library

[11]

11. M.J. Flynn, "Some computer organizations and their effectiveness," IEEE Trans. Comp., vol. C-21, pp. 948- 960, 1972.

[12]

12. B. Gendron and T.G. Crainic, "Parallel branch-and-bound algorithms: Survey and synthesis," Oper. Res., vol. 42, pp. 1042-1066, 1994.

Digital Library

[13]

13. A. Grama, V. Kumar, and P. Pardalos, "Parallel processing of discrete optimization problems," in Encyclopedia of Microcomputers, Marcel Dekker: New York, NY, pp. 129-157, 1992.

[14]

14. F.S. Hillier and G.J. Lieberman, Introduction to Operations Research, Holden-Day: San Francisco, CA, 1980.

Digital Library

[15]

15. W.D. Hillis, The Connection Machine, MIT Press: Cambridge, MA, 1985.

Digital Library

[16]

16. R.M. Karp and Y. Zhang, "Randomized parallel algorithms for backtrack search and branch-and-bound computation," J. Assoc. Comput. Mach., vol. 40, pp. 765-789, 1993.

Digital Library

[17]

17. G. Karypis and V. Kumar, "Unstructured tree search on SIMD parallel computers: A summary of results," in Proc. Supercomputing'92, Minneapolis, MN, 1992, pp. 453-462.

Digital Library

[18]

18. V. Kumar, K. Ramesh, and V. Nageshwara Rao, "Parallel best-first search of state-space graphs: A summary of results," in Proc. AAAI-88 Seventh Nat. Conf. Artif. Intel., St. Paul, MN, 1988.

[19]

19. V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms, Benjamin/Cummings: Redwood City, CA, 1994.

Digital Library

[20]

20. V. Kumar, G.Y. Ananth, and V. Nageshwara Rao, "Scalable load balancing techniques for parallel computers," J. Distrib. Parallel Comput., vol. 22, pp. 60-79, 1994.

Digital Library

[21]

21. A. Land and S. Powell, "Computer codes for problems of integer programming," in Discrete Optimization II, Annals of Discrete Mathematics, P.L. Hammer, E.L. Johnson, and B.H. Korte (Eds.), vol. 5, North-Holland: Amsterdam, 1979.

[22]

22. R. Lüling and B. Monien, "Load balancing for distributed branch and bound algorithms," in Proc. Int. Parallel Processing Symp., Beverly Hills, CA, 1992, pp. 543-549.

Digital Library

[23]

23. R. Lüling, B. Monien, and F. Ramme, "Load balancing in large networks: A comparative study," in Proc. 3rd IEEE Symp. Parallel and Distributed Processing, 1991, pp. 686-689.

Digital Library

[24]

24. A. Mahanti and C.J. Daniels, "A SIMD approach to parallel heuristic search," Artif. Intel., vol. 60, pp. 243-282, 1993.

Digital Library

[25]

25. V.J. Rayward-Smith, S.A. Rush, and G.P. McKeown, "Efficiency considerations in the implementation of parallel branch-and-bound," Ann. Oper. Res., vol. 43, pp. 123-145, 1993.

[26]

26. Thinking Machines Corporation, CMMD Reference Manual, Cambridge: MA, 1993 (Version 3.0).

[27]

27. S. Tschöke, R. Lüling, and B. Monien, "Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network," in Proc. 9th Int. Parallel Processing Symp., Santa Barbara, CA, 1995, pp. 182-189.

Digital Library

[28]

28. L.W. Tucker and A. Mainwaring, "CMMD: Active messages on the CM-5," Parallel Comput., vol. 20, pp. 481- 496, 1994.

Digital Library

[29]

29. T. von Eiken, D.E. Culler, S.C. Goldstein, and K.E. Schauser, "Active messages: A mechanism for integrated communication and computation," in Proc. 19th Int. Symp. Comp. Arch., Gold Coast, Australia, 1992.

Digital Library

[30]

30. O. Vornberger, "Load balancing on a network of transputers," in Proc. Second Annual Workshop on Distributed Algorithms, Amsterdam, 1987, pp. 116-126.

Digital Library

Cited By

Plimpton SHendrickson BStewart J(2004)A parallel rendezvous algorithm for interpolation between multiple gridsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.11.00664:2(266-276)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.11.006
Grama AKumar V(1999)State of the Art in Parallel Search Techniques for Discrete Optimization ProblemsIEEE Transactions on Knowledge and Data Engineering10.1109/69.75561211:1(28-35)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1109/69.755612
Plimpton SHendrickson BStewart JBrent RDuke D(1998)A parallel rendezvous algorithm for interpolation between multiple gridsProceedings of the 1998 ACM/IEEE conference on Supercomputing10.5555/509058.509110(1-8)Online publication date: 7-Nov-1998
https://dl.acm.org/doi/10.5555/509058.509110

Index Terms

Distributed versus Centralized Storage and Control forParallel Branch and Bound: Mixed Integer Programming on the CM-5

Recommendations

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we ...
Parallel Branch-and-Bound Algorithms for General Mixed Integer Programming on the CM-5

This “proof of concept” paper describes parallel solution of general mixed integer programs by a branch-and-bound algorithm on the CM-5 multiprocessing system. It goes beyond prior parallel branch-and-bound work by implementing a reasonably realistic ...
Multi-criteria branch and bound: A vector maximization algorithm for Mixed 0-1 Multiple Objective Linear Programming

The paper describes the Multi-Criteria Branch and Bound (MCBB) algorithm, a vector maximization algorithm capable of deriving all efficient extreme points, for small- and medium-sized Mixed 0-1 Multiple Objective Linear Programming (Mixed 0-1 MOLP). ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Optimization and Applications

Computational Optimization and Applications Volume 7, Issue 2

March 1997

87 pages

ISSN:0926-6003

Editor:
William W. Hager
Univ. of Florida

Issue’s Table of Contents

Copyright © Copyright © 1997 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 March 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Plimpton SHendrickson BStewart J(2004)A parallel rendezvous algorithm for interpolation between multiple gridsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.11.00664:2(266-276)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.11.006
Grama AKumar V(1999)State of the Art in Parallel Search Techniques for Discrete Optimization ProblemsIEEE Transactions on Knowledge and Data Engineering10.1109/69.75561211:1(28-35)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1109/69.755612
Plimpton SHendrickson BStewart JBrent RDuke D(1998)A parallel rendezvous algorithm for interpolation between multiple gridsProceedings of the 1998 ACM/IEEE conference on Supercomputing10.5555/509058.509110(1-8)Online publication date: 7-Nov-1998
https://dl.acm.org/doi/10.5555/509058.509110

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents