Branch-and-Bound Methods: A Survey

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 travel...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1966-08, Vol.14 (4), p.699-719
Main Authors: Lawler, E. L, Wood, D. E
Format: Article
Language:English
Subjects:
Algorithms
Cost allocation
Cost efficiency
Dynamic programming
Integer programming
Integers
Linear programming
Optimal solutions
Scheduling
Switching circuits
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.14.4.699