Consider the problem of locating m new facilities on a network to satisfy upper and/or lower bounds on distances between pairs of new and existing facilities and pairs of new facilities. Such constraints find applications in the solution of desirable and undesirable facility location problems as well as some mixed cases. The paper discusses theoretical, algorithmic, and complexity aspects of distance constraints, point out relations to minimax and maximin location, and present an algorithm that solves the problem if the imposed bounds induce a special structure.
