Alternative Formulation for the p-median Problem

Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem by a mixed integer linear problem. We show that this formulation, while it has the same value by LP-relaxation, can be much smaller in size than the classical formulation. A short computational experience carried on a set of benchmark instances shows that this new formulation can drastically improve the solution time of a branch-and-cut solution process by a commercial software.