Due to inevitable nondifferentiabilities, the minisum multifacility location
problem is regarded as hard to solve. It is shown that a certain
chararacterization of points at which nondifferentiabilities occur is
checkable in polynomial time. Therefore, it is possible to check efficiently
if several variables can be identified with each other, thereby reducing the
dimension of the problem and the number of nondifferentiable terms in the
objective function simultaneously. Numerical results confirm that by using
this strategy improved solutions can be found in less computation time.
Key Words. facility location, coincidence conditions, dimension reduction,
nondifferentiability detection, polynomial time algorithms,
numerical comparison