Vertex adjacencies in the set covering polyhedron

Abstract

We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvátal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.