A Dual-Based Procedure for Uncapacitated Facility Location

Abstract

We develop and test a method for the uncapacitated facility location problem that is based on a linear programming dual formation. A simple ascent and adjustment procedure frequently produces optimal dual solutions, which in turn often correspond directly to optimal integer primal solutions. If not, a branch-and-bound procedure completes the solution process. This approach has obtained and verified optimal solutions to all the Kuehn-Hamburger location problems in well under 0.1 seconds each on an IBM 360/91 computer, with no branching required. Computational tests on problems with as many as 100 potential facility locations provide evidence that this approach is superior to several other methods.