Lagrangean decomposition for integer programming theory and applications

Given a mixed-integer programming problem whose constraint set is the intersection of several specially structured constraint sets, it is possible to artificially induce decomposition in the Lagrangean relaxation problems by introducing copies of the original variables for a subset of constraints and dualizing the equivalence conditions between the original variables and the copies. The authors study duality for Lagrangean decomposition and compare it with conventional Lagrangean duality. The implications of Lagrangean decomposition can be quite profound for integer programming problems containing special classes of constraints such as subtour elimination constraints or matching inequalities. Several application problems exemplify the use of Lagrangean decomposition.