Certification of an optimal TSP tour through 85,900 cities
From MaRDI portal
Publication:1002076
DOI10.1016/j.orl.2008.09.006zbMath1154.90601OpenAlexW2018660239MaRDI QIDQ1002076
Keld Helsgaun, Vašek Chvátal, William Cook, Marcos Goycoolea, Robert E. Bixby, David L. Applegate, Daniel G. Espinoza
Publication date: 23 February 2009
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2008.09.006
Programming involving graphs or networks (90C35) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)
Related Items
On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem, A new class of hard problem instances for the 0-1 knapsack problem, Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, A learning based algorithm for drone routing, Orienteering for electioneering, The affine hull of the schedule polytope for servicing identical requests by parallel devices, “Make no little plans”: Impactful research to solve the next generation of transportation problems, Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals, Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals, Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem, Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework, Combinatorial integral approximation, Certifying algorithms, A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs, Special Frequency Quadrilaterals and an Application, Certificates of optimality for mixed integer linear programming using generalized subadditive generator functions, The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem, The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem, Learning to sparsify travelling salesman problem instances
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
- A new class of cutting planes for the symmetric travelling salesman problem
- Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
- Separating a Superclass of Comb Inequalities in Planar Graphs
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- On the symmetric travelling salesman problem I: Inequalities
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Small Travelling Salesman Polytopes
- Solution of a Large-Scale Traveling-Salesman Problem
- The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
- The traveling-salesman problem and minimum spanning trees: Part II
- Edmonds polytopes and weakly hamiltonian graphs
