Binding Inequalities for Tree Network Location Problems with Distance Constraints

In this paper, we consider the problem of finding locations of several new facilities in an imbedded tree network with respect to existing facilities at known locations so as to satisfy distance constraints, which impose upper bounds on distances between pairs of facilities. It is known that the existence of a feasible solution to the distance constraints is related to shortest paths through an auxiliary network. The arc lengths in this auxiliary network are the upper bounds on pairwise facility distances. This relationship takes the form of necessary and sufficient conditions, termed the separation conditions. We relate “tight” separation conditions to the solution of multifacility minimax location problems and efficient solutions to multiobjective multifacility location problems. In addition, we demonstrate how the multiobjective results provide insight into the question of lowest computational order of an algorithm for determining whether or not the distance constraints are consistent.