A projection method forl p norm location-allocation problems

We present a solution method for location-allocation problems involving thel_p norm, where 1 <p < . The method relaxes the {0, 1} constraints on the allocations, and solves for both the locations and allocations simultaneously. Necessary and sufficient conditions for local minima of the relaxed problem are stated and used to develop an iterative algorithm. This algorithm finds a stationary point on a series of subspaces defined by the current set of activities. The descent direction is a projection onto the current subspace of a direction incorporating second-order information for the locations, and first-order information for the allocations. Under mild conditions, the algorithm finds local minima with {0, 1} allocations and exhibits quadratic convergence. An implementation that exploits the special structure of these problems to dramatically reduce the computational cost of the required numerical linear algebra is described. Numerical results for thirty-six test problems are included.This research was supported in part by Natural Sciences and Engineering Research Council (NSERC) of Canada grants A-5671 and A-8639, and by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.