Global Optimization Procedures for the Capacitated Euclidean and l p Distance Multifacility Location-Allocation Problems

In this paper, we study the capacitated Euclidean and l p distance location-allocation problems. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design a branch-and-bound algorithm based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in this partial enumeration scheme, we employ two types of procedures. The first approach computes a lower bound via a projected location space subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities are generated in the allocation space, and objective function based cuts are derived in the location space to further tighten the lower bounding relaxation. The RLT procedure is then extended to the general l p distance problem, for p > 1. Computational experience is provided on a set of test problems to investigate both the projected location space and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances available in the literature for the Euclidean distance case, we report significantly improved solutions.