By way of subdifferential calculus, we reduce the problem of checking for coincidences in minisum multifacility location problems to the problem of constructing a maximal one-dimensional flow. In this way, the number of unknowns in a given problem can be reduced, simultaneously with the number of nondifferentiable terms in the objective function.

The new coincidence check makes use of the topology and the edge-weights of the facility interactions graph, only. It is shown that the algorithm proposed is best possible in the sense that any condition detecting more coincidences has to use additional properties of the underlying normed space. Moreover, the amount of work necessary to detect all embedding space-independent coincidences increases only polynomially in the problem size given.

Key Words. Coincidence conditions, multifacility location problem, optimality criteria, flow problems