A LAGRANGIAN HEURISTIC FOR THE CAPACITATED PLANT LOCATION PROBLEM WITH SINGLE-SOURCE CONSTRAINTS

In this paper we look at the Lagrangian relaxations of the Capacitated Plant Location Problem with Single Source constraints in terms of the bounds and solution techniques. We propose a heuristic based on a lagrangian relaxation of the problem. We also show how this heuristic can be used to solve other combinatorial problems that are related to this problem, such as the concentrator location problem and the bin packing problem.