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