On the integrality of the uncapacitated facility location polytope

Mourad Baiou(baioucust.univ-bpclermont.fr)
Francisco Barahona(barahonus.ibm.com)

Abstract: 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.

Keywords: facility location, polyhedral combinatorics

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Citation:

Download: [PDF]

Entry Submitted: 10/31/2007
Entry Accepted: 11/01/2007
Entry Last Modified: 10/31/2007

Modify/Update this entry