Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Andreello G., Caprara A., Fischetti M. Embedding {0, ½}-cuts in a branch-and-cut framework: A computational study. INFORMS J. Comput. (2007) 19:229–238Link, Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. Finding cuts in the TSP (A preliminary report). (1995) . DIMACS Report 95-05, Rutgers University, New Brunswick, NJGoogle Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Math. Programming (2003) 97:91–153Crossref, Google Scholar
• Barahona F., Mahjoub A. R. On the cut polytope. Math. Programming (1986) 36:157–173Crossref, Google Scholar
• Boyd S., Cockburn S., Vella D. On the domino-parity inequalities for the STSP. (2001) . Computer Science Technical Report TR-2001-10, University of Ottawa, Ottawa, CanadaGoogle Scholar
• Boyer J. M., Myrvold W. On the cutting edge: Simplified O(n) planarity by edge addition. J. Graph Algorithms Appl. (2004) 8:241–273Crossref, Google Scholar
• Chvátal V. Edmonds polytopes and weakly Hamiltonian graphs. Math. Programming (1973) 5:29–40Crossref, 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
• Fleischer L. K., Letchford A. N., Lodi A. Polynomial-time separation of a superclass of simple comb inequalities. Math. Oper. Res. (2006) 31:696–713Link, Google Scholar
• Grötschel M., Padberg M. W. On the symmetric traveling salesman problem I: Inequalities. Math. Programming (1979a) 16:265–280Crossref, Google Scholar
• Grötschel M., Padberg M. W. On the symmetric traveling salesman problem II: Lifting theorems and facets. Math. Programming (1979b) 16:281–302Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1993) 2nd ed.(Springer, Berlin, Germany) Crossref, Google Scholar
• Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. (2000) 126:106–130Crossref, Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M., Magnanti T., Monma C. L., Nemhauser G. The traveling salesman problem. Handbooks on Operations Research and Management Sciences: Networks (1995) (North Holland, Amsterdam, The Netherlands) 225–330Google Scholar
• Letchford A. N. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. (2000) 25:443–454Link, Google Scholar
• Letchford A. N., Pearson N. Exploiting planarity in separation routines for the symmetric traveling salesman problem. (2005) . Preprint, Department of Management Science, Lancaster University, Lancaster, UKGoogle 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., Wild E. The domino inequalities: Facets for the symmetric traveling salesman polytope. Math. Programming (2003) 98:223–251Crossref, 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., Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. (1991) 33:60–100Crossref, Google Scholar
• Reinelt G. TSPLIB—A traveling salesman library. ORSA J. Comput. (1991) 3:376–384Link, Google Scholar
• Tamaki H. Alternating cycle contribution: A tour-merging strategy for the travelling salesman problem. (2003) . Max-Planck Institute Research Report MPI-I-2003-1-007, Saarbrücken, GermanyGoogle Scholar
• Vella D.Using DP-Constraints to Obtain Improved TSP Solutions (2001) . M.S. thesis, School of Information Technology and Engineering, University of Ottawa, Ottawa, CanadaGoogle Scholar