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: | Conn A.R., Cornujols G. |
Keywords: | location |
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