On the p-Median Polytope and the Directed Odd Cycle Inequalities I: Triangle-Free Oriented Graphs

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

By: Mourad Baïou, Francisco Barahona

Published in: Discrete Optimization, volume 22, (no ), pages 206-224; SI 10.1016/j.disopt.2015.07.006 in 2016

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .