Abstract
J. F. Benders devised a clever approach for exploiting the structure of mathematical programming problems withcomplicating variables (variables which, when temporarily fixed, render the remaining optimization problem considerably more tractable). For the class of problems specifically considered by Benders, fixing the values of the complicating variables reduces the given problem to an ordinary linear program, parameterized, of course, by the value of the complicating variables vector. The algorithm he proposed for finding the optimal value of this vector employs a cutting-plane approach for building up adequate representations of (i) the extremal value of the linear program as a function of the parameterizing vector and (ii) the set of values of the parameterizing vector for which the linear program is feasible. Linear programming duality theory was employed to derive the natural families ofcuts characterizing these representations, and the parameterized linear program itself is used to generate what are usuallydeepest cuts for building up the representations.
In this paper, Benders' approach is generalized to a broader class of programs in which the parametrized subproblem need no longer be a linear program. Nonlinear convex duality theory is employed to derive the natural families of cuts corresponding to those in Benders' case. The conditions under which such a generalization is possible and appropriate are examined in detail. An illustrative specialization is made to the variable factor programming problem introduced by R. Wilson, where it offers an especially attractive approach. Preliminary computational experience is given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Geoffrion, A. M.,Elements of Large-Scale Mathematical Programming, Management Science, Vol. 16, No. 11, 1970.
Benders, J. F.,Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numerische Mathematik, Vol. 4, 1962.
Wilson, R. Programming Variable Factors, Management Science, Vol. 13, No. 1, 1966.
Balas, E.,Duality in Discrete Programming: IV. Applications, Carnegie-Mellon University, Graduate School of Industrial Administration, Report No. 145, 1968.
Meyer, R.,The Validity of a Family of Optimization Methods, SIAM Journal on Control, Vol. 8, No. 1, 1970.
Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
Geoffrion, A. M.,Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems, Operations Research, Vol. 18, No. 3, 1970.
Hogan, W.,Application of a General Convergence Theory for Outer Approximation Algorithms, University of California at Los Angeles, Western Management Science Institute, Working Paper No. 174, 1971.
Eaves, B. C., andZangwill, W. I.,Generalized Cutting Plane Algorithms, SIAM Journal on Control, Vol. 9, No. 4, 1971.
Geoffrion, A. M.,A New Global Optimization Technique for Gaseous Diffusion Plant Operation and Capital Investment, University of California at Los Angeles, Graduate School of Business Administration, Discussion Paper, 1970.
Geoffrion, A. M.,Duality in Nonlinear Programming: A Simplified Application-Oriented Development, SIAM Review, Vol. 13, No. 1, 1971.
Author information
Authors and Affiliations
Additional information
Communicated by A. V. Balakrishnan
An earlier version was presented at the Nonlinear Programming Symposium at the University of Wisconsin sponsored by the Mathematics Research Center, US Army, May 4–6, 1970. This research was supported by the National Science Foundation under Grant No. GP-8740.
Rights and permissions
About this article
Cite this article
Geoffrion, A.M. Generalized Benders decomposition. J Optim Theory Appl 10, 237–260 (1972). https://doi.org/10.1007/BF00934810
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00934810