The Travelling Salesman Problem and Its Variations
Contributors: Punnen, Abraham P.
Publisher: Springer
Published: 2002
Place of publication: Dordrecht
Language: eng
Format: [electronic resource]
Number of pages: 836
ISBN-13: 9780306482137
Subjects: Combinatorial optimization; Traveling-salesman problem
Description: This volume provides information on theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, and branch and bound, and branch and cut algorithms.
Notes: Description based upon print version of record.

Chapter 4 EXACT METHODS FOR THE ASYMMETRICTRAVELING SALESMAN PROBLEM
Table of contents: title: Title Page; Copyright Page; Table of Contents; Preface; Contributing Authors; Chapter 1 THE TRAVELING SALESMAN PROBLEM: APPLICATIONS, FORMULATIONSAND VARIATIONS; 1. Introduction; 1.1. The Shoelace Problem; title: A simple TSP; 2. Simple Variations of the TSP; 3. Applications of TSP; 3.1. Machine Scheduling Problems; 3.2. Cellular Manufacturing; 3.3. Arc Routing Problems; 3.4. Frequency Assignment Problem; 3.5. Structuring of Matrices; 3.6. Additional Applications; 4. Alternative representations of the TSP; 4.1. Linear programming representation; 4.2. Integer programming formulations; title: 4.3. Symmetric TSP4.4. Binary quadratic programming formulation; 4.5. Three Matroid Intersection; 5. Matrix Transformations; 6. More Variations of the TSP; Chapter 2 POLYHEDRAL THEORY AND BRANCH AND-CUT ALGORITHMS FORTHE SYMMETRIC TSP; 1. Introduction; 2. Integer linear programming models; 3. Introducing the symmetric TSP polytope andits various relaxations; 3.1. The symmetric TSP polytope; 3.2. The monotone Relaxation; 3.3. The Hamiltonian path relaxation; 3.4. The graphical relaxation; 4. The graphical relaxation Framework; 4.1. General theorems; 4.2. Composition of inequalities; title: 4.3. Node lifting5. The Comb inequalities; 6. The Star and Path inequahties; 7. The Clique Tree and Bipartition inequalities; 8. The Ladder inequalities; 9. A general approach to some TSP validinequalities; 10. A unifying family of inequalities; 11. Domino inequalities; 12. Other inequalities; 13. The separation problem; 14. Greedy heuristic for minimum cut; 15. Graph associated to a vector x* G M^; 16. Heuristics for Comb Separation; 16.1. The biconnected component heuristic; 16.2. The max-back Heuristic; 16.3. The Ear Heuristic; 16.4. About minimum cuts; 16.5. The Domino Heuristic; title: 16.6. The Consecutive Ones Heuristic17. Separation of multi-handle inequalities; 17.1. How do multiple handles help?; 18. Separation outside the template paradigm; 19. Branch-and-Cut implementation of theSTSP; 19.1. Variables; 19.2. Constraints; 19.3. Upperbounding; 19.4. Branching; 20. Computational results; 21. Conclusion; Chapter 3 POLYHEDRAL THEORY FOR THE ASYMMETRIC TRAVELING SALESMANPROBLEM; 1. Introduction; 2. Basic ATS inequalities; 2.1. Symmetric Inequalities; 2.2. Asymmetric inequalities; 3. The monotone ATS polytope; 3.1. Monotonizations of polyhedra; title: 3.2. Properties of the monotone ATS polytope4. Facet-lifting procedures; 4.1. Cloning and clique lifting; 4.2. T-lifting; 4.3. Merge lifting; 4.4. Two-cycle cloning; 5. Equivalence of inequalities and canonicalforms; 6. Odd closed alternating trail inequalities; 7. Source-destination inequalities; 8. Lifted cycle inequalities; 8.1. Two-liftable chord sets; 8.2. Maximally 2-lifted cycle inequalities; 8.3. Maximally 2-lifted cycle inequalities of rank1; 8.4. Maximally 2-lifted cycle inequalities of unbounded rank; Acknowledgements