A projection method for the uncapacitated facility location problem

A projection method for the uncapacitated facility location problem

0.00 Avg rating0 Votes
Article ID: iaor1991662
Country: Netherlands
Volume: 46
Issue: 3
Start Page Number: 273
End Page Number: 298
Publication Date: Apr 1990
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: location
Abstract:

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program in m variables and constraints, where m is the number of clients. For comparison, the underlying linear programming dual has mn+m+n variables and mn+n constraints, where n is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.

Reviews

Required fields are marked *. Your email address will not be published.