The Potential of Lagrangean Decomposition

This paper first presents Lagrangean decomposition as a tool for obtaining bounds for (mixed-)integer programming problems with linear constraints and with linear or nonlinear objective functions. We assume that the constraint set is split into multiple subsets of constraints. Conditions under which strong bounds can be obtained are presented. Applications with linear and nonlinear objective functions are reviewed. Computational results are presented for some of these problems.