Duality and Distance Constraints for the Nonlinear p-Center Problem and Covering Problem on a Tree Network

The problem of locating a fixed number, p, of facilities (centers) on a network, where there are constraints on the center locations and where the centers provide a service to customers (demand points) located at vertices of the network is addressed. The cost or “loss” of servicing a given demand point is a nonlinear function of the distance between the demand point and the closest center. We consider the case where the network has special structure (a tree network), i.e., there is a unique shortest path between any two points on the network. We also provide and interpret a dual to this problem and give polynomially bounded procedures for solving both problems. The primal location problem is solved with the aid of a related problem for which we also give a dual.