GENERALIZED BENDERS DECOMPOSITION
Abstract
J. F. Benders devised an approach for exploiting the structure of mathematical programming problems with 'complicating variables'. Such problems have the property that temporarily fixing the values of certain variables renders the remaining optimization problem considerably more tractable--perhaps breaking apart into a number of independent smaller problems, or being solvable by a highly efficient known algorithm, or reducing to a convex program in continuous variables whereas the original problem is partly nonconvex or discrete. In this paper, Benders' approach is generalized to a broader class of programs in which the parameterized 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 are examined in detail from both the theoretical and computational viewpoints. An illustrative specialization is made to the variable factor programming problem introduced by R. Wilson, where it appears to offer an especially attractive approach.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1970
- Accession Number
- AD0708878
Entities
People
- Arthur M. Geoffrion
Organizations
- University of California, Los Angeles