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 Chvatal 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.

Minor revision, 22 pages, 3 figures

References in corpus (1)

• Addendum to Vertex adjacencies in the set covering polyhedron

Cited by in corpus (10)

• On vertex adjacencies in the polytope of pyramidal tours with step-backs
• Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
• On the Graph of the Pedigree Polytope
• Addendum to Vertex adjacencies in the set covering polyhedron
• An iterative ILP approach for constructing a Hamiltonian decomposition of a regular multigraph
• Backtracking algorithms for constructing the Hamiltonian decomposition of a 4-regular multigraph
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• On the diameter of the polytope of the stable marriage with ties
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search