Adjacency on combinatorial polyhedra

This paper shows some useful properties of the adjacency structures of a class of combinatorial polyhedra including the equality constrained 0-1 polytopes. The class of polyhedra considered here includes 0-1 polytopes related to some combinatorial optimization problems: e.g., set partitioning polytopes, set packing polytopes, perfect matching polytopes, vertex packing polytopes and all the faces of these polytopes. First, the authors establish two fundamenal properties of the equality constrained 0-1 polytopes. This paper deals with the polyhedra satisfying these two fundamenal properties. They consider a path on the polyhedron satisfying the condition that for each co-ordinate, the vertices in a path form a monotonic sequence. When one of the end vertices of the path is optimal to an optimization problem defined on the polyhedron, the associated objective values form a monotonic sequence and the length of the path is bounded by the dimension of the polytope. In a sense some of the results in this paper are natural extensions of the properties of the set partitioning polytopes showed by Balas and Padberg. However, different from the studies of Balas and Padberg, the present proofs are not based on the pivot operations. Next, the authors prove the monotone Hirsch conjecture for the combinatorial polyhedra considered here. In the last section, they show that the monotone Hirsch conjecture is true for all 0-1 polytopes.