On the p-median polytope and the odd directed cycle inequalities: Oriented graphs

Abstract

We study the classical linear programing relaxation of the p-median problem, together with the so-called “odd directed cycle inequalities.” We characterize in terms of forbidden subgraphs, the oriented graphs for which this system of inequalities defines an integral polytope. This completes the study started in Baïou and Barahona (2016), where oriented graphs with no triangles were treated.