Fractional vertices, cuts and facets of the simple plant location problem

Abstract

This paper investigates the structure of the Integer Programming Polytope of an uncapacitated (simple) plant location problem. One can describe families of fractional vertices and derive from them valid inequalities for the integer problem. Some of these will actually be shown to be facets of the integer polytope. Also some families of SPLP with large duality gaps will be described, together with facets which bridge these gaps. Much of the motivation stems from algorithmic work in which the exploitation of “good” cutting planes within a direct dual algorithm have been shown to be of crucial importance.