The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints

References

• Applegate DL, Bixby R, Chvátal V, Cook W (2003) Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Math. Programming 97(1):91–153.Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2007) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook W, Espinoza DG, Goycoolea M, Helsgaun K (2009) Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 37(1):11–15.Google Scholar
• Balas E, Toth P (1983) Branch and bound methods for the traveling salesman problem. Technical report, Carnegie Mellon University, Graduate School of Industrial Administration, Pittsburgh, PA.Google Scholar
• Bellmore M, Nemhauser GL (1968) The traveling salesman problem: A survey. Oper. Res. 16(3):538–558.Link, Google Scholar
• Bentley JL (1992) Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. 4(4):387–411.Link, Google Scholar
• Bérczi K (2012) The triangle-free 2-matching polytope of subcubic graphs. Technical Report TR-2012-02, Egerváry Research Group on Combinatorial Optimization, Budapest, Hungary.Google Scholar
• Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, CMU, Pittsburgh, PA.Google Scholar
• Chvátal V, Cook W, Hartmann M (1989) On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114–115:455–499. Google Scholar
• Cook WJ, Hartmann M (1990) On the complexity of branch and cut methods for the traveling salesman problem. Cook WJ, Seymour P, eds. Polyhedral Combinatorics, vol. 1 (American Mathematical Society, Providence, RI), 75–82.Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2(4):393–410.Link, Google Scholar
• Dey SS, Dubey Y, Molinaro M (2023) Lower bounds on the size of general branch-and-bound trees. Math. Programming 198(1):539–559.Google Scholar
• Dimitrovski F (2023) elkai—A Python library for solving TSP problems. Accessed September 2025, https://pypi.org/project/elkai/.Google Scholar
• Eastman WL (1958) Linear programming with pattern constraints: A thesis. Unpublished PhD thesis, Harvard University, Cambridge, MA.Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. Sect. B Math. Math. Phys. 69B(1 and 2):125.Google Scholar
• Gabow HN (2018) Data structures for weighted matching and extensions to b-matching and f-factors. ACM Trans. Algorithms 14(3):1–80.Google Scholar
• Garfinkel RS (1973) On partitioning the feasible set in a branch-and-bound algorithm for the asymmetric traveling-salesman problem. Oper. Res. 21(1):340–343.Abstract, Google Scholar
• Grotschel M, Holland O (1987) A cutting plane algorithm for minimum perfect 2-matchings. Computing 39(4):327–344.Google Scholar
• Grötschel M, Holland O (1991) Solution of large-scale symmetric travelling salesman problems. Math. Programming 51(1):141–202.Google Scholar
• Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, 2nd ed. (Springer-Verlag, Berlin).Google Scholar
• Gurobi (2023) Gurobi optimizer reference manual. Accessed September 2025, https://www.gurobi.com.Google Scholar
• Hartvigsen D, Li Y (2013) Polyhedron of triangle-free simple 2-matchings in subcubic graphs. Math. Programming 138:43–82.Google Scholar
• Helsgaun K (2000) An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1):106–130.Google Scholar
• Helsgaun K (2009) General k-opt submoves for the Lin–Kernighan TSP heuristic. Math. Programming Comput. 1:119–163.Google Scholar
• Johnson DS, McGeoch LA (2002) Experimental analysis of heuristics for the STSP. Gutin G, Punnen AP, eds. The Traveling Salesman Problem and its Variations (Springer, Boston), 369–443.Google Scholar
• Kaibel V, Weltge S (2015) Lower bounds on the sizes of integer programs without additional variables. Math. Programming 154(1):407–425.Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity Comput. Comput.: Proc. Sympos. Complexity Comput. Comput. (Springer, Boston), 85–103.Google Scholar
• Kobayashi Y (2010) A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs. Discrete Optim. 7(4):197–202.Google Scholar
• Kobayashi Y (2022) Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles. Math. Programming 192(1):675–702.Google Scholar
• Laporte G (1992) The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2):231–247.Google Scholar
• Miliotis P (1976) Integer programming approaches to the travelling salesman problem. Math. Programming 10(1):367–378.Google Scholar
• Murty KG (1968) An algorithm for ranking all the assignments in order of increasing cost. Oper. Res. 16(3):682–687.Abstract, Google Scholar
• Papadimitriou CH (1992) The complexity of the Lin–Kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21(3):450–465.Google Scholar
• Papadimitriou CH, Steiglitz K (1977) On the complexity of local search for the traveling salesman problem. SIAM J. Comput. 6(1):76–83.Google Scholar
• Pferschy U, Staněk R (2017) Generating subtour elimination constraints for the TSP from pure integer solutions. Central Eur. J. Oper. Res. 25(1):231–260.Google Scholar
• Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24 (Springer Science & Business Media, New York).Google Scholar
• Taillard ÉD, Helsgaun K (2019) POPMUSIC for the travelling salesman problem. Eur. J. Oper. Res. 272(2):420–429.Google Scholar
• Tinós R, Helsgaun K, Whitley D (2018) Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic. Internat. Conf. Parallel Problem Solving from Nature (Springer International Publishing, Cham, Switzerland), 95–107.Google Scholar
• Traub V, Vygen J (2024) Approximation Algorithms for Traveling Salesman Problems (Cambridge University Press).Google Scholar
• Vercesi E, Gualandi S, Mastrolilli M, Gambardella LM (2023) On the generation of metric TSP instances with a large integrality gap by branch-and-cut. Math. Programming Comput. 15(2):389–416.Google Scholar
• Vornberger O (1980) Easy and hard cycle covers. Technical report, Universität/Gesamthochschule Paderborn, Germany.Google Scholar
• Zhong X (2025) Lower bounds on the integrality ratio of the subtour LP for the traveling salesman problem. Discrete Appl. Math. 365:109–129.Google Scholar