The p-median polytope of restricted Y-graphs
Mourad Baiou (baioucustsv.univ-bpclermont.fr)
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 )
Entry Submitted: 03/09/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|