An Evaluation of the Dual as a Lower Bound in Facilities Location Problems

Abstract

Several methods have been proposed and tested for calculating lower bounds on the objective function of facilities location 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 pre-determined fraction of the optimal solution. Recently, the dual of the facilities location problem has been proposed as an alternative method for computing lower bounds. In this paper, the dual is compared with three other lower bounds.