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.

+More

combinatorial optimization stsp tour hamiltonian cycles multistage insertion formulation pedigrees pedigree polytope its structure membership problem convex hull 01 polytopes polyhedral structure symmetric traveling salesman problem instance pedigree approach

Tiru S. Arthanari,.ON PEDIGREE POLYTOPE AND ITS PROPERTIES. 91 (S2),.

Tiru S. Arthanari,"ON PEDIGREE POLYTOPE AND ITS PROPERTIES" 91

Tiru S. Arthanari,"ON PEDIGREE POLYTOPE AND ITS PROPERTIES"