Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5128302 | Discrete Optimization | 2016 | 19 Pages |
Abstract
We study the effect of the odd directed cycle inequalities in the description of the polytope associated with the p-median problem. We treat oriented graphs, i.e., if (u,v) is in the arc-set, then (v,u) is not in the arc-set. We characterize the oriented graphs for which the obvious linear relaxation together with the directed odd cycle inequalities describe the p-median polytope. This study has two parts: in this paper we treat triangle-free graphs, then in a second paper we use induction on the number of triangles to treat general oriented graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Mourad Baïou, Francisco Barahona,