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 po lytopes related to some combinatorial optimization problems; e.g., set partitioning polytopes, set packing polytopes, perfect matching polyt opes, vertex packing polytopes and all the faces of these polytopes. F irst, we establish two fundamental properties of the equality constrai ned 0-1 polytopes. This paper deals with the polyhedra satisfying thes e two fundamental properties. We consider a path on the polyhedron sat isfying the condition that for each co-ordinate, the vertices in a pat h form a monotonic sequence, When one of the end vertices of the path is optimal to an optimization problem defined on the polyhedron, the a ssociated objective values form a monotonic sequence and the length of the path is bounded by the dimension of the polytope. In a sense, som e of the results in this paper are natural extensions of the propertie s of the set partitioning polytopes showed by Balas and Padberg. Howev er, different from the studies of Balas and Padberg, our proofs are no t based on the pivot operations. Next, we prove the monotone Hirsch co njecture for the combinatorial polyhedra considered here. In the last section, we show that the monotone Hirsch conjecture is true for all 0 -1 polytopes.