E-book
The Traveling Salesman Problem and Its Variations [electronic resource] / edited by Gregory Gutin, Abraham P. Punnen.
Record details
- ISBN: 9780306482137
- Physical Description: XXXVI, 829 p. online resource.
- Publisher: Boston, MA : Springer US : 2007.
Search for related items by subject
Search for related items by series
Electronic resources
| 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 |
