On pedigree polytope and its properties
|
| Title | On pedigree polytope and its properties |
| Authors | |
| 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. |
| Publisher | Accademia Peloritana dei Pericolanti |
| Date | 2013-07-26 |
| Source | 0365-0359 |
| Rights | Articles and conference papers published in Atti della Accademia Peloritana dei Pericolanti – Classe di Scienze Fisiche, Matematiche e Naturali are distributed under the terms and conditions of a Creative Commons Attribution 3.0 Unported License (effective since 2009, Vol. 87). Correspondingly, authors who publish with this journal agree to the following terms:Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work´s authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal´s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access). |