Alternative Formulation for the p-median Problem

Sourour Elloumi (elloumicnam.fr)

Abstract: 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.

Keywords: Facility Location, $p$-median, Integer Programming, Formulation

Category 1: Combinatorial Optimization

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Citation:

Download:

Entry Submitted: 12/16/2005
Entry Accepted: 12/18/2005
Entry Last Modified: 11/08/2007

Modify/Update this entry