On the uncapacitated facility location problem

Abstract

The objective of this study is to broaden the applicability of the uncapacitated facility location problem to real-world problems, by developing efficient solution methods for it and providing a way to use the model of this problem for a more realistic location problem. For this purpose, two approaches for obtaining strong lower bounds are developed, both of which have not been tested for the problem yet. In addition, we show that the model of the uncapacitated facility location problem can be used without modification for dealing with a more realistic stochastic problem. First, we introduce a conceptually new method of generating strong cuts for the problem. Based on its special structure, we generate inequalities which even cut off part of the integer feasible region but still provide valid and sharp lower bounds of the problem when added to its linear programming relaxation. Also shown is the relation between such inequalities and the conventional valid inequalities of the problem. Secondly, we present an algorithm of incorporating valid inequalities for solving the problem which can minimize the computational difficulties involved when implementing such inequalities. Heuristics of identifying the violated valid inequalities and solving the successive linear programming relaxation augmented with the inequalities will be developed. The efficiency of the proposed algorithm is analyzed through computing experiments with a number of sample problems. Thirdly, an alternative way of obtaining strong lower bounds for the problem is developed by using the so-called ``penalty`` concept developed in integer programming. Unlike the traditional way of calculating penalties, we present a method which can take advantage of structural properties of the problem. The proposed algorithm will also be tested by solving some test problems. Finally, we present an alternative formulation of the deterministic location model which Tcha and Yoon have recently developed to approxim...