Premium
On the p ‐median polytope and the odd directed cycle inequalities: Oriented graphs
Author(s) -
Baïou Mourad,
Barahona Francisco
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21813
Subject(s) - polytope , combinatorics , mathematics , birkhoff polytope , inequality , discrete mathematics , geometry , mathematical analysis , convex set , convex optimization , regular polygon
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.