Applying Lagrangian relaxation to the resolution of two-stage location problems

A family of two-stage location problems is considered. These problems involve a system providing a choice of depots and/or plants, each with an associated location cost, and a set of demands points which must be supplied, in such a way that the total cost is minimized. By using Lagrangian relaxation, lower bounds and heuristic solutions are obtained for two kinds of formulation involving two or three indexes for each transportation variable. The goodness of both formulations is compared by means of a computational study, and the results for several instances are presented.