Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

By David L. Applegate, Robert E. Bixby, V. Chvátal, W. Cook. 2003

192 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Industrial and Manufacturing Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

Citations in the corpus

Neural Combinatorial Optimization with Reinforcement Learning (2016, background): “…2006), widely accepted as one of the best exact TSP solvers, makes use of cutting plane algorithms (Dantzig et al., 1954; Padberg & Rinaldi, 1990; Applegate et al., 2003), iteratively solving linear programming relaxations of the TSP, in conjunction with a branch-and-bound approach that prunes…”
A Multi-Facet Survey on Memetic Computation (2011, background): “[116] which is designed for solving traveling salesman prob-”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “…TSP solvers such as Concorde [Applegate et al., 2006] make use of cutting plane algorithms [Dantzig et al., 1954, Padberg and Rinaldi, 1991, Applegate et al., 2003] to iteratively solve linear programming relaxations of the TSP in addition to a branch-and-bound approach that reduces the…”
General k-opt submoves for the Lin–Kernighan TSP heuristic (2009, methodology): “Using cutting-plane methods Concorde [1,3] has found a lower bound of 713,056, 616 for the 1,000,000-city instance E1M.0 (William Cook, private communication, 2008).”
Certification of an optimal TSP tour through 85, 900 cities (2009, methodology): “The technique used in [1] was developed for hypergraph inequalities; we generalize it to handle domino-parity inequalities.”
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches (2010, methodology): “…formulation for TSP. Incidentally, an early description of Concorde, which is recognized as the most performing exact algorithm currently available, was published under the title ‘Implementing the Dantzig–Fulkerson–Johnson algorithm for large traveling salesman problems’ (Applegate et al., 2003).”