Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation

References

• Applegate D., Bixby R. E., Chvátal V., Cook W. Project and lift (preliminary report). (1998) . Technical report, Computer Sciences. Rutgers University, New Brunswick, NJ.Google Scholar
• Applegate D., Bixby R. E., Chvátal V., Cook W. TSP cuts outside the template paradigm. (2000) . Technical report, Computer Sciences. Rutgers University, New Brunswick, NJ. http://www.cs.rutgers.edu/∼chvatal/dagstuhl.psGoogle Scholar
• Boyd S., Cunningham W. Small traveling salesman polytopes. Math. Oper. Res. (1991) 16:259–271Link, Google Scholar
• Caprara A., Fischetti M., Letchford A. N. On the separation of maximally violated mod-k cuts. Math. Programming (2000) 87:37–56Crossref, Google Scholar
• Carr R. Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope. (1995) . Ph.D. thesis, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Carr R. Separating over classes of TSP inequalities defined by 0-node lifting in polynomial time. IPCO Proc. IPCO Conference (1996) Vancouver, British Columbia:460–474Crossref, 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
• Carr R. Some results on node lifting of TSP inequalities. J. Combin. Optim. (2000) 4(4):395–414Crossref, Google Scholar
• Carr R., Vempala S. Towards a 4/3 approximation for the asymmetric traveling salesman problem. SODA Conference (2000) San Francisco, CA:116–125Google Scholar
• Cornuejols 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
• Edmonds J. Maximum matching and a polyhedron with 0-1 vertices. J. Res. National Bureau Standards (1965) 69B:125–130Crossref, Google Scholar
• Fleischer L., Tardos E. Separating maximally violated comb inequalities in planar graphs. Math. Oper. Res. (1999) 24(1):130–148Link, Google Scholar
• Goemans M. X. Worst-case comparison of valid inequalities for the TSP. Math. Programming (1995) 69:335–349Crossref, Google Scholar
• Gomory R. E., Hu T. C. Multi-terminal network flows. SIAM J. Appl. Math. (1961) 9:551–570Crossref, Google Scholar
• Grötschel M., Padberg M. W. On the symmetric traveling salesman problem II: Lifting theorems and facets. Math. Programming (1979) 16:282–302Google Scholar
• Groetschel M., Lovasz L., Schrijver A. J.Geometric Algorithms and Combinatorial Optimization (1988) (Wiley, New York) Crossref, Google Scholar
• Johnson D. S., Papadimitriou C. H., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Computational complexity. The Traveling Salesman Problem (1985) (John Wiley & Sons, Chichester, U.K.) 37–85Google 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 OR & MS (1995) 7(Elsevier Science B.V., Amsterdam, The Netherlands) 225–330Crossref, Google Scholar
• Letchford A. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. (2000) 25(3):443–454Link, Google Scholar
• Letchford A., Lodi A. Polynomial-time separation of simple comb inequalities. IPCO Proc., 2002 (2002) Cambridge, MA:93–108Crossref, Google Scholar
• Naddef D., Clochard J. M. Some fast and efficient heuristics for comb separation in the symmetric traveling salesman problem. (1994) . Tech. Rep., Université Joseph Fourier Grenoble I, Grenoble, France.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
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (Wiley, New York) Crossref, Google Scholar
• Padberg M. W., Rao M. R. Odd minimum cut sets and b-matchings. Math. Oper. Res. (1982) 7:67–80Link, Google Scholar
• Padberg M. W., Rinaldi G. A branch-and-cut approach to a traveling salesman problem with side constraints. Management Sci. (1989) 35(11):1393–1412Link, Google Scholar
• Padberg M. W., Rinaldi G. Facet identification for the symmetric traveling salesman polytope. Math. Programming (1990) 47:219–257Crossref, Google Scholar
• Yannakakis M. Expressing combinatorial optimization problems by linear programs. J. Comp. System Sci. (1991) 43:441–466Crossref, Google Scholar