Mathematical Programming Approaches to the Traveling Salesman Problem
作者： Adam N Letchford , Andrea Lodi , None
DOI: 10.1002/9780470400531.EORMS0505
关键词: Integer programming 、 Polyhedral combinatorics 、 Travelling salesman problem 、 Mathematics 、 2-opt 、 Bottleneck traveling salesman problem 、 Mathematical optimization 、 Combinatorial optimization
摘要: The Traveling Salesman Problem or TSP is a fundamental and well-known problem in combinatorial optimization. At present, the most successful algorithms for solving large-scale instances of to proven (near-)optimality are based on integer programming. This entry introduces main theoretical algorithmic tools involved. Topics covered include: formulations TSP, polyhedral theory, separation routines, exact algorithms. Keywords: traveling salesman problem; integer programming; polyhedral combinatorics
sci-hub.se 参考文章(41)
Martin Grötschel, On the symmetric travelling salesman problem: Solution of a 120-city problem Mathematical Programming Studies. pp. 61- 77 ,(1980) , 10.1007/BFB0120887
Matteo Fischetti, Andrea Lodi, Paolo Toth, Exact Methods for the Asymmetric Traveling Salesman Problem Combinatorial Optimization. pp. 169- 205 ,(2007) , 10.1007/0-306-48213-4_4
David Shmoys, Eugene L. Lawler, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, The traveling salesman problem ,(1985)
Jan Karel Lenstra, David Shmoys, The Traveling Salesman Problem: A Computational Study ,(2007)
The traveling salesman problem and its variations Kluwer Academic. ,(2007) , 10.1007/B101971
Michael Jünger, Gerhard Reinelt, Giovanni Rinaldi, Chapter 4 The traveling salesman problem Handbooks in Operations Research and Management Science. ,vol. 7, pp. 225- 330 ,(1995) , 10.1016/S0927-0507(05)80121-5
Gerhard Reinelt, The traveling salesman: computational solutions for TSP applications Springer-Verlag. ,(1994)
Denis Naddef, Stefan Thienel, Efficient separation routines for the symmetric traveling salesman problem II: separating multi handle inequalities Mathematical Programming. ,vol. 92, pp. 257- 283 ,(2002) , 10.1007/S101070100276
Robert Carr, Separating Clique Trees and Bipartition Inequalities Having a Fixed Number of Handles and Teeth in Polynomial Time Mathematics of Operations Research. ,vol. 22, pp. 257- 265 ,(1997) , 10.1287/MOOR.22.2.257
Manfred Padberg, Giovanni Rinaldi, Facet identification for the symmetric traveling salesman polytope Mathematical Programming. ,vol. 47, pp. 219- 257 ,(1990) , 10.1007/BF01580861