A method for solving to optimality uncapacitated location problems

In this paper the authors develop a method for solving to optimality a general 0-1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times. The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage. The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, the p-median problem and the fixed-charge p-median problem. Computational results are given for problems of up to the size 200 customers×200 potential facility sites.