Generalized Domino-Parity Inequalities for the Symmetric Traveling Salesman Problem

References

• Appel K., Haken W.Contemporary Mathematics: Every Planar Map Is Four Colorable (1989) 98(American Mathematical Society, Providence, RI) Crossref, Google Scholar
• Applegate D. L., Bixby R. E., Chvátal V., Cook W. J.The Traveling Salesman Problem: A Computational Study (2006) (Princeton University Press, Princeton, NJ) Google Scholar
• Boyd S., Cunningham W. H. Small travelling salesman polytopes. Math. Oper. Res. (1991) 16(2):259–271Link, Google Scholar
• Boyd S. C., Cockburn S., Vella D. On the domino-parity inequalities for the STSP. Math. Programming (2006) 110(3):501–519Crossref, Google Scholar
• Carr R. Separating clique trees and bipartition inequalities having a fixed number of handles and teeth in polynomial time. Math. Oper. Res. (1997) 22(2):257–265Link, Google Scholar
• Chvátal V. Edmonds polytopes and weakly Hamiltonian graphs. Math. Programming (1973) 5:29–40Crossref, Google Scholar
• Cook W. J., Espinoza D. G., Goycoolea M. Computing with domino-parity inequalities for the TSP. INFORMS J. Comput. (2007) 17:356–365Link, Google 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
• Cunningham W., Wang Y. Restricted 2-factor polytopes. Math. Programming (2000) 87:87–111Crossref, Google Scholar
• Dantzig G., Fulkerson R., Johnson S. Solution of a large-scale traveling salesman problem. Oper. Res. (1954) 2:393–410Link, Google Scholar
• Fleischer L., Tardos É. Separating maximally violated comb inequalities in planar graphs. Math. Oper. Res. (1999) 24:130–148Link, Google Scholar
• Fleischmann B. A new class of cutting planes for the symmetric traveling salesman problem. Math. Programming (1988) 40:225–246Crossref, Google Scholar
• Gerards A. M., Schrijver A. Matrices with the Edmonds-Johnson property. Combinatorica (1986) 6:365–379Crossref, Google Scholar
• Goycoolea M. Cutting planes for large mixed integer programming models. (2006) . Ph.D. thesis, Georgia Institute of Technology, AtlantaGoogle Scholar
• Grötschel M., Padberg M. W. On the symmetric traveling 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., Magnanti T. L., Monma C. L., Nemhauser G. L. The traveling salesman problem. Handbook of Operations Research (1995) (North Holland, Amsterdam, The Netherlands) 225–330Google Scholar
• Karger D. A new approach to the minimum cut problem. J. ACM (1996) 43:601–640Crossref, Google Scholar
• Letchford A. N. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. (2000) 25:443–454Link, Google Scholar
• Mohar B., Thomassen C.Graphs on Surfaces (2001) (Johns Hopkins University Press, Baltimore) Crossref, Google Scholar
• Naddef D., Gutin G., Punnen A. Polyhedral theory and branch-and-cut algorithms for the symmetric traveling salesman problem. The Traveling Salesman Problem and Its Variations (2002) (Kluwer, Dordrecht, The Netherlands) 29–116Google Scholar
• Naddef D., Groetschel M. The domino inequalities for the symmetric traveling salesman polytope. The Sharpest Cut: The Impact of Mandred Padberg and His Work. MPS—SIAM Series on Optimization (2004) (Society for Industrial and Applied Mathematics, Philadelphia) 153–172Crossref, Google Scholar
• Naddef D., Rinaldi G. The symmetric traveling salesman polytope: New facets from the graphical relaxation. Math. Oper. Res. (2007) 32:233–256Link, Google Scholar
• Naddef D., Wild E. The domino inequalities: Facets for the symmetric traveling salesman polytope. Math. Programming (2003) 98:223–251Crossref, Google Scholar
• Nagamochi H., Nishimura K., Ibaraki T. Computing all small cuts in undirected networks. SIAM J. Discrete Math. (1997) 10(3):469–481Crossref, Google Scholar
• Schrijver A. Combinatorial optimization: Polyhedra and efficiency. Volume A: Paths, Flows, Matchings (2003) (Springer, Berlin) . Chapters 1–38Google Scholar