On pedigree polytope and its properties

Abstract

The fact that linear optimization over a polytope can be done in polynomial time in the input size of the instance, has created renewed interest in studying 0-1 polytopes corresponding to combinatorial optimization problems.  Studying their polyhedral structure has resulted in new algorithms to solve very large instances of some difficult problems like the symmetric traveling salesman problem. The multistage insertion formulation (MI) given by the author, in 1982, for the symmetric traveling salesman problem (STSP), gives rise to a combinatorial object called the pedigree. The pedigrees are in one-to-one correspondence with Hamiltonian cycles. Given n, the convex hull of all the pedigrees is called the corresponding pedigree polytope. In this article we bring together the research done a little over a decade by the author and his doctoral students, on the pedigree polytope, its structure, membership problem and properties of the MI formulation for the STSP. In addition we summarise some of the computational and other peripheral results relating to pedigree approach to solve the STSP. The pedigree polytope possesses properties not shared by the STSP (tour) polytope, which makes it interesting to study the pedigrees, both from theoretical and algorithmic perspectives.