Optimization Online


On the p-median polytope of a special class of graphs

Mourad Baiou (mourad.baiou***at***custsv.univ-bpclermont.fr)
Francisco Barahona (barahon***at***us.ibm.com)

Abstract: In this paper we consider a well known class of valid inequalities for the p-median and the uncapacitated facility location polytopes, the odd cycle inequalities. It is known that their separation problem is polynomially solvable. We give a new polynomial separation algorithm based on a reduction from the original graph. Then, we define a nontrivial class of graphs, where the odd cycle inequalities together with the linear relaxations of both the p-median and uncapacitated facility location problems, suffice to describe the associated polytope. To do this, we first give a complete description of the fractional extreme points of the linear relaxation for the p-median polytope in that class of graphs.

Keywords: p-median problem, facility location

Category 1: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 03/09/2006
Entry Accepted: 03/09/2006
Entry Last Modified: 03/09/2006

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