The p-median polytope of restricted Y-graphs

Mourad Baiou (baioucustsv.univ-bpclermont.fr)
Francisco Barahona (barahonus.ibm.com)

Abstract: We further study the effect of odd cycle inequalities in the description of the polytopes associated with the p-median and uncapacitated facility location problems. We show that the obvious integer linear programming formulation together with the odd cycle inequalities completely describe these polytopes for the class of restricted Y-graphs. This extends our results for the class of Y-free graphs. We also obtain a characterization of both polytopes for a bidirected path.

Keywords: p-median problem, uncapacitated facility location problem, odd cycle inequalities.

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