Abstract
The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification and various issues arising from sequential and parallel implementations of branch-and-bound kernels.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Agin, Optimum seeking with branch-and-bound, Manag. Sci. 13(1966)B176-B185.
A.V. Aho, J.E. Hopcroft and J.D. Ullman,Data Structures and Algorithms (Addison-Wesley, 1982).
A. Balakrishnan and N.R. Patel, Problem reduction methods and a tree generation algorithm for the Steiner network problem, Networks 17(1987)65–85.
E. Balas, An additive algorithm for solving linear programs with zero-one variables, Oper. Res. 13(1965)517–526.
E. Balas, A note on the branch-and-bound principle, Oper. Res. 16(1968)442–445.
E. Balas and P. Toth, Branch and bound methods, in:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. Lawler, Lenstra, Rinnooy Kan and Shmoys (Wiley, London, 1985), pp. 361–401.
J.E. Beasley, An SST-based algorithm for the Steiner problem in graphs, Networks 19(1989)1–16.
F.W. Burton, G.P. McKeown, V.J. Rayward-Smith and M.R. Sleep, Parallel processing and combinatorial optimisation,Proc. CO81 Conf., Stirling University (1982).
J. Clausen and J.L. Träff, Implementation of parallel branch-and-bound algorithms — experiences with the graph partitioning problem, NATO/ARW on Topological Network Design, Copenhagen (1989), Ann. Oper. Res., this volume.
R.J. Dakin, A tree-search algorithm for mixed-integer programming problems, Comp. J. 8(1965)250–255.
C.W. Duin and A. Volgenaut, Reduction tests for the Steiner problem in graphs, Department of Operations Research, Faculty of Economic Sciences and Econometrics, University of Amsterdam (1988).
R. Finkel and U. Manber, DIB — a distributed implementation of backtracking, ACM Trans. Prog. Languages and Systems 9(1987)235–256.
P.E. Hart, N. Nilsson and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Systems and Cybernetics 4(1968)100–107.
E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms (Computer Science Press, Rockville, MD, 1978).
R.J.M. Hughes, Why functional programming matters, Comp. J. 32(1989)98–107.
F.K. Hwang and D. Richards, a two-volume collection of important works in the area of Steiner trees, to appear in the series:Advances in Discrete Mathematics and Computer Science (Hadronic Press).
T. Ibaraki, Branch-and-bound procedure and state-space representation of combinatorial optimization problems, Information and Control 36(1978)1–27.
T. Ibaraki, Implementation and concurrent execution of branch-and-bound algorithms, Ann. Oper. Res. 10/11(1987), ch. 9.
R.M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher (Plenum Press, New York, 1972), pp. 85–103.
W.H. Kohler and K. Steiglitz, Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, J. ACM 21(1974)140–156.
V. Kumar and L.N. Kanal, A general branch-and-bound formulation for understanding and synthesizing AND/OR tree search procedures, Artificial Intelligence 21(1983)179–198.
T.H. Lai and S. Sahni, Anomalies in parallel branch-and-bound algorithms, CACM 27(1984).
T.H. Lai and A. Sprague, A note on anomalies in parallel branch-and-bound algorithms with one-to-one bounding functions, Inf. Proc. Lett. 23(1986)119–122.
A.H. Land and A.G. Doig, An automatic method of solving discrete programming problems, Econometrica 28(1960)497–520.
E.L. Lawler and D.E. Wood, Branch-and-bound methods: A survey, Oper. Res. 14(1966)699–719.
G.-J. Li and B.W. Wah, Coping with anomalies in parallel branch-and-bound algorithms, IEEE Trans. Comp. C-35(1986)568–573.
G.-J. Li and B.W. Wah, Computational efficiency of parallel approximate branch-and-bound algorithms,Proc. 1984 Int. Conf. on Parallel Processing (1984), pp. 473–480.
I. Marshall and P. Messer, Conventions for generic abstract data type modules in Modula-2, School of Information Systems, University of East Anglia, Norwich, in preparation.
G.P. McKeown, V.J. Rayward-Smith, S.A. Rush and H.J. Turpin, A framework for the implementation of parallel integer programming branch-and-bound on a transputer rack, submitted for publication.
L.G. Mitten, Branch-and-bound methods: General formulation and properties, Oper. Res. 18(1970)24–34.
D.S. Nau, V. Kumar and L. Kanal, General branch-and-bound, and its relation to A* and AO*, Artificial Intelligence 23(1984)29–58.
N.J. Nilsson,Problem-solving Methods in Artificial Intelligence (McGraw-Hill, New York, 1971).
J. Plesnik, A bound for the Steiner tree problem in graphs, Math. Slovaca 31(1981)155–163.
R.C. Prim, Shortest connection networks and some generalizations, Bell. Syst. Tech. J. 36(1957)1389–1401.
M.J. Quinn,Designing Efficient Algorithms for Parallel Computers (McGraw-Hill, New York, 1987).
V.J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs, Int. J. Math. Educ. Sci. Tech. 14(1983)15–23.
V.J. Rayward-Smith and A. Clare, On finding Steiner vertices, Networks 16(1986)283–294.
V.J. Rayward-Smith, G.P. McKeown and F.W. Burton, The general problem solving algorithm and its implementation, New Generation Computing 6(1988)41–66.
E.M. Reingold, J. Nievergelt and N. Deo,Combinatorial Algorithms: Theory and Practice (Prentice-Hall, Englewood Cliffs, NJ, 1977).
J.F. Shapiro,Mathematical Programming: Structures and Algorithms (Wiley, New York, 1979).
M.L. Shore, L.R. Foulds and P.B. Gibbons, An algorithm for the Steiner problem in graphs, Networks 12(1982)323–333.
H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica 24(1980)573–577.
H.J. Turpin, The branch-and-bound paradigm, Ph.D. Thesis, School of Information Systems, University of East Anglia, Norwich (1990).
H.J. Turpin, G.P. McKeown, V.J. Rayward-Smith and S.A. Rush, Branch-and-bound on a transputer rack, submitted for publication.
B.W. Wah, G.-J. Li and C.F. Yu, Multiprocessing of combinatorial search problems, IEEE Computer 18(1985).
B.W. Wah and Y.W.E. Ma, MANIP — a multicomputer architecture for solving combinatorial extremum-search problems, IEEE Trans. Comp. C-33(1984)377–390.
B.M. Waxman and M. Imase, Worst-case performance of Rayward-Smith's Steiner tree heuristic, Inf. Proc. Lett. 29(1988)283–287.
Y.F. Wu, P. Widmayer and C.K. Wong, A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica 23(1986)223–229.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
McKeown, G.P., Rayward-Smith, V.J. & Turpin, H.J. Branch-and-bound as a higher-order function. Ann Oper Res 33, 379–402 (1991). https://doi.org/10.1007/BF02073942
Issue Date:
DOI: https://doi.org/10.1007/BF02073942