Lagrangean decomposition in integer linear programming: A new scheme

The authors present a new Lagrangean decomposition scheme for integer linear programming problems. This scheme is based on a reformulation of the problem by introducing one or more copies of some of the decision variables and a number of coupling constraints. By defining a Lagrangean relaxation of the copy and coupling constraints, it is possible to decompose the Lagrangean problem into one or more independent subproblems. There are substantially fewer Lagrangean multipliers than primal variables. The bounds given by this scheme are compared with other Lagrangean decompositions and with classical Lagrangean relaxation.