On the integrality of some facility location polytopes

Abstract

We study a system of linear inequalities associated with some facility location problemS. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycleS. We also derive odd cycle inequalities and give a separation algorithm. © 2009 Society for Industrial and Applied Mathematics.