An optimal solution for the Uncapacitated Facility Location Problem using the dual formulation

In this paper we develop a simple method which provides a solution for the Uncapacitated Facility Location Problem (UFLP). This method is based on two procedures, namely the dual ascent procedure and the dual adjustment procedure. The dual ascent procedure is executed first, if this procedure does not find an optimal solution, then this solution is improved by the dual adjustment procedure. We test this method on three standard problem instances of the UFLP, namely the Bilde-Krarup, the Galvão Raggi and the Gap B instances in order to check if this method works for different instances. We also check what happens to the number of established facilities and the total costs if the opening costs and the transportation costs increase or decrease.