Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141837 | Discrete Optimization | 2008 | 15 Pages |
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 non-trivial 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 this class of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Mourad Baïou, Francisco Barahona,