Solving Nonlinear Single-Facility Network Location Problems

We present a general approach to solving nonlinear single-facility network location problems. We assume that cost is any convex function of distances, and solve this class of problem by solving convex subproblems on “treelike segments” into which the network is decomposed. We show that only a fraction of treelike segments generally need be examined, and that our method results in a reasonably efficient general-purpose algorithm. The algorithm is particularly effective on real-world (as opposed to random) networks, and when the cost function is nondecreasing and “semiseparable,” as are many popular cost functions. Finally, we describe theoretical complexity bounds and computational experience.