Lagranian decomposition based heuristic for the generalized assignment problem

This paper defines a new Lagrangian heuristic for the generalized assignment problem (GAP). The heuristic is based on a Lagrangian decomposition of the problem in which a substitution of variables is performed and the constraints defining the substituted variables are then dualized in a Lagrangian relaxation of the problem. With the inclusion of new constraints (implied by the original constraints), the relaxation decomposes into two subproblems which can be solved in polynomial time. A standard subgradient optimization algorithm is applied to this relaxation, which when used with the Mazzola heuristic forms the new heuristic for the GAP. The computational results, performed on a standard set of test problems, indicate that the new heuristic is competitive with the set partitioning heuristic of Cattrysse et al.