DECOMPOSITION IN GENERAL MATHEMATICAL-PROGRAMMING

In this paper a unifying framework is presented for the generalization of the decomposition methods originally developed by Benders (1962) a nd Dantzig and Wolfe (1960). These generalizations, called Variable De composition and Constraint Decomposition respectively, are based on th e general duality theory developed by Tind and Wolsey. The framework p resented is of a general nature since there are no restrictive conditi ons imposed on problem structure; moreover, inaccuracies and duality g aps that are encountered during computations are accounted for. The tw o decomposition methods are proven not to cycle if certain (fairly gen eral) conditions are met. Furthermore, finite convergence can be ensur ed under the traditional finiteness conditions and asymptotic converge nce can be guaranteed once certain continuity conditions are met. The obvious symmetry between both types of decomposition methods is explai ned by establishing a duality relation between the two, which extends a similar result in Linear Programming. A remaining asymmetry in the a symptotic convergence results is argued to be a direct consequence of a fundamental asymmetry that resides in the Tind-Wolsey duality theory . It can be shown that in case the latter asymmetry disappears, the fo r-mer does too. Other decomposition techniques, such as Lagrangean Dec omposition and Cross Decomposition, turn out to be captured by the gen eral framework presented here as well.