Variable decomposition, constraint decomposition and cross decomposition in general mathematical programming (Q4035629)

Two basic decomposition approaches have been given by Benders (1962) and Dantzig and Wolfe (1960) for mathematical programming problems of the type \(\text{Max}_ x f(x)\) subject to \(G(x)\odot 0\), \(x\in X\), where \(X\subseteq R^ n\), \(\odot \in\{\leq,=\}\), \(f: X\to R\cup\{\pm\infty\}\) and \(G: X\to R^ m\), \(G=(G_ 1,\dots,G_ m)^ T\). The authors introduce two generalizations of these approaches, the variable and constraint decomposition, respectively. Convergence properties of the consequent procedures are established. Further, a cross decomposition which intermediate between the two procedures is investigated. The results are established in an abstract setting and provide a good background for further research on the decomposition technique. For the entire collection see [Zbl 0752.00053].