Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope

The pedigree is a combinatorial object defined over the cartesian product of certain subsets of edges in a complete graph. There is a 1–1 correspondence between the pedigrees and Hamiltonian cycles (tours) in a complete graph. Linear optimization over Hamiltonian cycles, also known as the symmetric traveling salesman problem (STSPSTSP) has several 0–1 integer and mixed integer formulations. The Multistage Insertion formulation (MI-formulationMI-formulation) is one such 0–1 integer formulation of the STSPSTSP. Any solution to the MIMI-formulation is a pedigree and vice versa. However the polytope corresponding to the pedigrees has properties not shared by the STSPSTSP polytope. For instance, (i) the pedigree polytope is a combinatorial polytope, in the sense, given any two nonadjacent vertices of the polytope W1,W2W1,W2, we can find two other nonadjacent vertices, W3,W4W3,W4, such that W1+W2=W3+W4W1+W2=W3+W4 and (ii) testing the nonadjacency of tours is an NPNP-complete problem, while the corresponding problem for the pedigrees is strongly polynomial. In this paper we demonstrate how the study of the nonadjacency structure is useful in understanding that of the tour polytope. We prove that a sufficiency condition for nonadjacency in the tour polytope is nonadjacency of the corresponding pedigrees in the pedigree polytope. This proof makes explicit use of properties of both the pedigree polytope and the MI-relaxationMI-relaxation problem.