Branch-and-Bound Methods: A Survey
Operations ResearchPublished 1 August 1966
Eugene L. Lawler, Derek Wood
Citations1,982
SJR quartileQ1
SJR score2.56
SNIP1.83
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
Abstract
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (Land-Doig and Balas methods), nonlinear programming (minimization of nonconvex objective functions), the traveling-salesman problem (Eastman and Little, et al. methods), and the quadratic assignment problem (Gilmore and Lawler methods). Computational considerations, including trade-offs between length of computation and storage requirements, are discussed and a comparison with dynamic programming is made. Various applications outside the domain of mathematical programming are also mentioned.
Keywords
Computer ScienceMathematicsEngineering
IBM Journal of Research and DevelopmentSome Studies in Machine Learning Using the Game of Checkers
4,355 Citations1959Arthur L. Samuel
A new signature-table technique is described together with an improved book-learning procedure which is thought to be much superior to the linear polynomial method and to permit the program to look ahead to a much greater depth than it otherwise could do.
An Automatic Method for Solving Discrete Programming Problems
1,997 Citations2009A. H. Land, Alison Doig
Bell System Technical JournalMinimization of Boolean Functions*
1,226 Citations1956E.J. McCluskey
A systematic procedure is presented for writing a Boolean function as a minimum sum of products and specific attention is given to terms which can be included in the function solely for the designer's convenience.
Operations ResearchA Linear Programming Approach to the Cutting Stock Problem—Part II
1,102 Citations1963Paul C. Gilmore, Ralph E. Gomory
The paper describes a new and faster knapsack method, experiments, and formulation changes, and the introduction of a rational objective function when customers' orders are not for fixed amounts, but rather for a range of amounts.
Operations ResearchAn Algorithm for the Traveling Salesman Problem
1,049 Citations1963John D. C. Little, Katta G. Murty +2 more
A “branch and bound” algorithm is presented for solving the traveling salesman problem, where the set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching.
Journal of the ACMDynamic Programming Treatment of the Travelling Salesman Problem
783 Citations1962Richard Bellman
This problem can be formulated in dynamic programming terms, and resolved computationally for up to 17 cities, and combined with various simple manipulations may be used to obtain quick approximate solutions.
Operations ResearchAn Additive Algorithm for Solving Linear Programs with Zero-One Variables
705 Citations1965Egon Balas
The Computer JournalA tree-search algorithm for mixed integer programming problems
638 Citations1965R. J. Dakin
Operations ResearchApplication of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems
589 Citations1965Edward Ignall, Linus Schrage
The branch-and-bound technique of Little, et al. and Land and Doig is presented and then applied to two flow-shop scheduling problems and results for up to 10 jobs are given, including comparisons with other techniques.
Journal of the ACMBacktrack Programming
485 Citations1965Solomon W. Golomb, L. D. Baumert
A widely used method of efftcient search is examined in detail and its scope and methods are formulated in their full generality.
Journal of the Society for Industrial and Applied MathematicsOptimal and Suboptimal Algorithms for the Quadratic Assignment Problem
441 Citations1962Paul C. Gilmore
Operations ResearchA Branch-Bound Algorithm for Plant Location
426 Citations1966M. A. Efroymson, T. L. Ray
An integer-programming method for solving a special class of discrete programming problems called plant location is discussed, which has been successfully used to solve "practical" location problems with upwards of fifty plants.
AN ALGORITHM FOR THE MIXED INTEGER PROBLEM
350 Citations1960Ralph E. Gomory
IBM Journal of Research and DevelopmentMinimization Over Boolean Graphs
264 Citations1962J. P. Roth, Richard M. Karp
A general approach to functional decomposition is given and efficient tests for the detection of decompositions are derived and these results are employed in the development of an alphabetic search procedure for determining minimum-cost Boolean graphs which satisfy any given design specifications.
Journal of the Operational Research SocietyA “Branch-and-Bound” Algorithm for the Exact Solution of the Three-Machine Scheduling Problem
243 Citations1965Z. A. Łomnicki
By combining Roy's graph-theoretical interpretation of the problem of job scheduling on machines and some general results of his theory with the “branch-and-bound” method recently applied by Little et al. to the travelling salesman problem an algorithm has been obtained for the exact solution of the scheduling problem in the case of three machines.
SIAM ReviewInteger Programming by Implicit Enumeration and Balas’ Method
221 Citations1967Arthur M. Geoffrion
The present reformulation of the essentials of Balas' algorithm for the zero-one integer linear programming problem is based upon the idea of 'elementary tree search' that has been used by Glover as the basis for his multiphase-dual algorithm.
Management ScienceAn Algorithm for the Solution of Mixed Integer Programming Problems
140 Citations1966Norman J. Driebeek
An algorithm is presented for the solution of mixed integer programming problems which contain a large number of continuous variables in addition to a few variables that are restricted to discrete values.
Transactions of the American Mathematical SocietyAlgebraic topological methods for the synthesis of switching systems. I
85 Citations1958J. P. Roth
The problem of synthesis of switching systems is considered as being inherently of a combinatorial topological character and from this point of view yields a mechanization and visualization of the problen not evident from the logical approach.
Management ScienceThree Heuristic Rules for Sequencing Jobs to a Single Production Facility
84 Citations1965J. William Gavett
The study consists of examining the performance of the three heuristic rules in terms of the optimal downtime obtained by the branch and bound algorithm and the downtime which results from a random sequencing of jobs through the facility.
Journal of the Operational Research SocietyA Problem of Assignment with Inter-Related Costs
51 Citations1963A. H. Land
There is a class of assignment problems where the cost function depends on the assignment of pairs of variables and a method of finding the optimum solution by a systematic exploration of a limited part of the solution space is presented by means of a numerical example.
Naval Research Logistics QuarterlyLinear programming in bid evaluation
46 Citations1954Edward Stanley, D. P. Honig +1 more
It is shown how the recently developed mathematical discipline of linear programming can be applied to problems in Government procurement agency to determine the allocation of contracts which would result in the lowest over-all cost to the Government.
IBM Journal of Research and DevelopmentMinimization over Boolean Trees
28 Citations1960J. P. Roth
An algorithm is provided for what might be termea tne general problem ot logical design ot circuits with one output and no feedback, believed to be efficient on problems with eight or less variables.
A computer program for the synthesis of combinational switching circuits
28 Citations1961Richard M. Karp, F. E. McFarlin +2 more
This paper describes an IBM 7090 program for the design of single output combinational switching circuits for arbitrary sets of primitive logical elements, designed so that the most promising sequences are investigated first.
IBM Journal of Research and DevelopmentAlgebraic Topological Methods for the Synthesis of Switching Systems—Part III: Minimization of Nonsingular Boolean Trees
21 Citations1959J. P. Roth, Eric G. Wagner
An algorithm is given for solving a general problem in combinational switching-circuit minimization theory, which consists of a disjunction of trees of any set of logical elements so that in any given tree no input appears more than once.