A PROJECTION METHOD FOR L(P) NORM LOCATION-ALLOCATION PROBLEMS

We present a solution method for location-allocation problems involvin g the l(p) norm, where 1 <p <infinity. The method relaxes the {0, 1} c onstraints on the allocations, and solves for both the locations and a llocations simultaneously. Necessary and sufficient conditions for loc al minima of the relaxed problem are stated and used to develop an ite rative algorithm. This algorithm finds a stationary point on a series of subspaces defined by the current set of activities. The descent dir ection is a projection onto the current subspace of a direction incorp orating second-order information for the locations, and first-order in formation for the allocations. Under mild conditions, the algorithm fi nds local minima with {0, 1} allocations and exhibits quadratic conver gence. 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-s ix test problems are included.