On the integrality of the uncapacitated facility location polytope

We study a system of linear inequalities associated with the uncapacitated facility location problem. 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.

Article

Download

View PDF