Generalized Benders decomposition
Tóm tắt
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.
Tài liệu tham khảo
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.