An edition of The Travelling Salesman Problem and Its Variations
(2002)
The Travelling Salesman Problem and Its Variations
by Gregory Gutin
- 0 Ratings
- 0 Want to read
- 0 Currently reading
- 0 Have read
Share
×Close
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.
Check nearby libraries
Buy this book
Previews available in: English
Showing 1 featured edition. View all 1 editions?
| Edition | Availability |
|---|---|
1
The Travelling Salesman Problem and Its Variations
2002, Springer
electronic resource
in English
0306482134 9780306482137
|
aaaa
Libraries near you:
WorldCat
|
Book Details
Table of Contents
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
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
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
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
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
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
Edition Notes
Description based upon print version of record.
Chapter 4 EXACT METHODS FOR THE ASYMMETRICTRAVELING SALESMAN PROBLEM
Classifications
External Links
The Physical Object
ID Numbers
Community Reviews (0)
Feedback?
History
- Created July 7, 2019
- 2 revisions
Wikipedia citation
×CloseCopy and paste this code into your Wikipedia page. Need help?
| February 25, 2022 | Edited by ImportBot | import existing book |
| July 7, 2019 | Created by MARC Bot | Imported from Internet Archive item record |