Abstract
The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.H. Ahrens and G. Finke, “Merging and sorting applied to the zero–one knapsack problem”,Operations Research 23 (1975) 1099–1109.
O.G. Alekseev and I.F. Volodos, “Combined use of dynamic programming and branch-andbound methods in discrete programming problems”,Automation and Remote Control 37 (4) Pt. 2 (1976) 557–565.
N. Christofides, “A minimax-facility location problem and the cardinality constrained set covering problem”, Management Science Research Report No. 375, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1975).
E.V. Denardo and B.L. Fox, “Shortest route methods: reaching, pruning, and buckets”, Yale University (May 1977).
V. Dharmadhikari, “Discrete dynamic programming and the nonlinear resource allocation problem”, Technical Report CP-74009, Dept. of Computer Science and Operations Research, Southern Methodist University, Dallas, TX (1974).
S.E. Elmaghraby, “The one-machine sequencing problem with delay costs”,Journal of Industrial Engineering 19 (1968) 105–108.
M.L. Fisher, “A dual algorithm for the one-machine scheduling problem”,Mathematical Programming 11 (1976) 229–251.
R.S. Garfinkel and G.L. Nemhauser,Integer Programming (Wiley—Interscience, New York, 1972).
A.M. Geoffrion and R.E. Marsten, “Integer programming algorithms: a framework and state-of-the art survey”,Management Science 18 (1972) 465–491.
F. Glover, “Improved linear integer programming formulations of nonlinear integer problems”,Management Science 22 (1975) 455–460.
R.E. Haymond, “Discontinuities in the optimal return in dynamic programming”,Journal of Mathematical Analysis and Applications 30 (1970) 639–644.
F.S. Hillier, “Efficient heuristic procedures for integer linear programming with an interior”,Operations Research 17 (1969) 600–637.
T. Ibaraki, “The power of dominance relations in branch-and-bound algorithms”,Journal of the Association for Computing Machinery 24 (1977) 264–279.
E. Ignall and L. Schrage, “Application of the branch-and-bound technique to some flow-shop scheduling problems”,Operations Research 11 (1965) 400–412.
G.A. Kochenberger, B.A. McCarl, and F.P. Wyman, “A heuristic for general integer programming”,Decision Sciences 5 (1974) 36–44.
M.J. Magazine, G.L. Nemhauser, and L.E. Trotter, Jr., “When the greedy solution solves a class of knapsack problems”,Operations Research 23 (1975) 207–217.
R.E. Marsten, “SEXOP: subroutines for experimental optimization”, Sloan School of Management, MIT, Cambridge, MA (1974).
R.E. Marsten and T.L. Morin, “Parametric integer programming: the right-hand-side case”,Annals of Discrete Mathematics 1 (1977) 375–390.
L.G. Mitten and A.R. Warburton, “Implicit enumeration procedures”, Working Paper 251, Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, B.C., Canada (1973).
T.L. Morin and A.M.O. Esogbue, “The imbedded state space approach to reducing dimensionality in dynamic programs of higher dimensions”,Journal of Mathematical Analysis and Applications 48 (1974) 801–810.
T.L. Morin and R.E. Marsten, “An algorithm for nonlinear knapsack problems”,Management Science 22 (1976) 1147–1158.
T.L. Morin and R.E. Marsten, “Branch-and-bound strategies for dynamic programming”,Operations Research 24 (1976) 611–627.
G.L. Nemhauser, “A generalized permanent label setting algorithm for the shortest path between specified nodes”,Journal of Mathematical Analysis and Applications 38 (1972) 328–334.
G.L. Nemhauser and Z. Ullman, “Discrete dynamic programming and capital allocation”,Management Science 15 (1969) 494–505.
C.C. Petersen, “Computational experience with variants of the Balas algorithm applied to the selection of R & D project”,Management Science 13 (1967) 736–750.
C.C. Petersen, “A capital budgeting heuristic algorithm using exchange operations”,AIIE Transactions 6 (1974) 143–150.
F. Proschan and T.A. Bray, “Optimal redundancy under multiple constraints”,Operations Research 13 (1965) 143–150.
H.M. Salkin and C.A. DeKluyver, “The knapsack problem: a survey”,Naval Research Logistics Quarterly 22 (1975) 127–144.
S. Senju and Y. Toyoda, “An approach to linear programming with 0/1 variables”,Management Science 15 (1968) B196-B207.
Y. Toyoda, “A simplified algorithm for obtaining approximate solutions to zero–one programming problems”,Management Science 21 (1975) 1417–1427.
H.M. Weingartner and D.N. Ness, “Methods for the solution of the multi-dimensional 0/1 knapsack problem”,Operations Research 15 (1967) 83–103.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Marsten, R.E., Morin, T.L. A hybrid approach to discrete mathematical programming. Mathematical Programming 14, 21–40 (1978). https://doi.org/10.1007/BF01588949
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588949