Bounding Methods for Facilities Location Problems

Abstract

Several methods have been proposed and tested for calculating lower bounds on the objective function of facilities problems. These methods contribute to the efficiency of iterative solution methods by allowing the user to terminate the computation process when the objective function comes within a predetermined fraction of the optimal solution. Two of the existing bounding methods have been presented only for single facility location models with Euclidean (straight-line) distances. One of these methods uses the dual of the single facility location model to compute a lower bound. This thesis introduces a method for generating a feasible dual solution from any primal solution by means of a projection matrix. The projection matrix method is applied to single and multi-facility models. The second bounding method, which involves the solution of a rectilinear distance model to obtain a lower bound, is extended in this thesis to include a generalized, distance function and the multi-facility situation. Computation results for the two new bounding methods are compared with several existing bounding methods. These results should aid practitioners in selecting an appropriate bounding method for an iterative solution method to a facilities location problem.