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

Mourad Baiou (mourad.baioucustsv.univ-bpclermont.fr)
Francisco Barahona (barahonus.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 )

Citation:

Download: [PDF]

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

Modify/Update this entry