Optimization Online


Alternative Formulation for the p-median Problem

Sourour Elloumi (elloumi***at***cnam.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 )



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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society