1992 | OriginalPaper | Chapter
Variable Decomposition, Constraint Decomposition and Cross Decomposition in General Mathematical Programming
Authors : Olaf E. Flippo, Alexander H. G. Rinnooy Kan
Published in: Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.