The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation

References

• Balas E., Fischetti M. On the monotonization of polyhedra. Math. Programming (1997) 77:59–84Crossref, Google Scholar
• Christof T., Reinelt G. Combinatorial optimization and small polytopes. TOP (1996) 4:1–53Crossref, Google Scholar
• Chvátal V. Edmonds polytopes and weakly Hamiltonian graphs. Math. Programming (1973) 5:29–40Crossref, Google Scholar
• Clochard J. M., Naddef D., Rinaldi G., Wolsey L. A. Using path inequalities in a branch and cut code for the symmetric traveling salesman problem. Proc. 3rd Math. Programming Conf. Integer Programming Combin. Optim. (1993) (CORE, Louvain-la-Neuve, Belgium) 291–311Google Scholar
• Cornuéjols G., Fonlupt J., Naddef D. The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming (1985) 33:1–27Crossref, Google Scholar
• Goemans M. X. Worst-case comparison of valid inequalities for the TSP. Math. Programming (1995) 69:335–349Crossref, Google Scholar
• Grötschel M. On the monotone symmetric travelling salesman problem: Hypohamiltonian/hypotraceable graphs and facets. Math. Oper. Res. (1980) 5:285–292Link, Google Scholar
• Grötschel M., Lovász L., Graham R. L., Grötschel M., Lovász L. Combinatorial optimization. Handbook of Combinatorics (1995) II(North-Holland, Amsterdam, The Netherlands) 1541–1597Chap. 28Google Scholar
• Grötschel M., Padberg M. W. On the symmetric travelling salesman problem I: Inequalities. Math. Programming (1979) 16:265–280Crossref, Google Scholar
• Grötschel M., Padberg M. W. On the symmetric travelling salesman problem II: Lifting theorems and facets. Math. Programming (1979) 16:281–302Crossref, Google Scholar
• Grötschel M., Pulleyblank W. R. Clique tree inequalities and the symmetric travelling salesman problem. Math. Oper. Res. (1986) 11:537–569Link, Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. The traveling salesman problem. Network Models, Handbooks in Operations Research and Management Science (1995) 7(North-Holland, Amsterdam, The Netherlands) 225–330Chap. 4Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.The Traveling Salesman Problem. Wiley-Interscience Series in Discrete Mathematics (1985) (John Wiley & Sons, Chichester) Google Scholar
• Naddef D., Gutin G., Punnen A. Polyhedral theory, branch and cut algorithms for the symmetric traveling salesman problem. The Traveling Salesman Problem and Its Variations. Combinatorial Optimization (2002) (Kluwer Academic Publisher, Dordrecht, The Netherlands) 29–116Google Scholar
• Naddef D., Pochet Y. The symmetric traveling salesman polytope revisited. Math. Oper. Res. (2001) 26:700–722Link, Google Scholar
• Naddef D., Rinaldi G. The symmetric traveling salesman polytope: New facets from the graphical relaxation. (1988) . Technical Report 248, IASI-CNR, Rome, ItalyGoogle Scholar
• Naddef D., Rinaldi G. The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities. Math. Programming (1991) 51:359–400Crossref, Google Scholar
• Naddef D., Rinaldi G. The graphical relaxation: A new framework for the symmetric traveling salesman polytope. Math. Programming (1993) 58:53–88Crossref, Google Scholar
• Naddef D., Thienel S. Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation. Math. Programming (2002) 92(2):237–255Crossref, Google Scholar
• Naddef D., Thienel S. Efficient separation routines for the symmetric traveling salesman problem. II: Separating multihandle inequalities. Math. Programming (2002) 92(2):257–283Crossref, Google Scholar
• Naddef D., Wild E. The domino inequalities: Facets for the symmetric traveling salesman polytope. Math. Programming (2003) 98:223–251Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization. Discrete Mathematics and Optimization (1988) (Wiley-Interscience, New York) Google Scholar
• Oswald M., Reinelt G., Theis D. O., Jünger M., Kaibel V. Not every GTSP facet induces a STSP facet. Integer Programming & Combinatorial Optimization (IPCO) XI, Lecture Notes in Computer Science (2005) 3509(Springer-Verlag GmbH, Berlin, Germany) 468–482Crossref, Google Scholar
• Padberg M. W., Hong S. On the symmetric travelling salesman problem: A computational study. Math. Programming Stud. (1980) 12:78–107Crossref, Google Scholar