Variable Decomposition, Constraint Decomposition and Cross Decomposition in General Mathematical Programming

Decomposition has been recognized as a fundamental technique in optimization ever since the seminal papers of Benders (1962) and Dantzig & Wolfe (1960). The literature abounds with theoretical extensions of these two basic approaches, as well as with reports of successful applications (for references, see Flippo (1991)). In this paper, Variable and Constraint Decomposition will be introduced as proper generalizations of Benders Decomposition and Dantzig-Wolfe Decomposition respectively. Under fairly mild conditions, these methods can be prevented from exhibiting cyclic behavior, and under much stronger conditions, they can be proven to converge asymptotically or even finitely. Special attention will be paid to Cross Decomposition, which is intermediate between the two decomposition methods mentioned above. A number of convergence criteria will be shown to prevent the procedure from cycling, or even to enforce asymptotic or finite convergence.