scientific article; zbMATH DE number 3943560
[For the entire collection see Zbl 0562.00014.] This chapter focuses on the computational aspects of the polyhedral theory developed in Chapter 8 of this book [see the preceding review] for the traveling salesman problem. The problem is now that of finding facet- including linear inequalities to be used, for instance, in a cutting plane algorithm using linear programming techniques. The authors first study the number of facets of TSP polytopes. One does not know a complete system of facet-inducing inequalities, but it is even impossible to list all known ones, because of their huge number. Yet in order to prove optimality of a given vertex, one only needs a suitable set of facet-inducing inequalities. Suitable constraints (facet-inducing, rather than just valid inequalities) must be generated on the fly if one wants to use LP techniques. The authors discuss the equivalence of optimization and algorithmic facet identification, based on the ellipsoid algorithm. The next two sections deal with identification of subtour elimination constraints and of clique tree inequalities. Heuristic and exact (polynomial) procedures for the solution of the subtour problem are described. For the case of the general clique tree inequalities, the facet identification problem is not solved to date nor is there any nontrivial heuristic for it. However there are a polynomial algorithm and heuristics for identifying 2-matching constraints and there is a heuristic for comb constraints. The final section gives an account of what has been done in terms of applying the polyhedral theory for the TSP to numerical problem solving. The solution of a 120-city problem by a relaxation method without recourse to branch-and-bound is described in detail. Computation of lower bounds for 74 TSP's and solution of 10 large scale problems are then discussed. The authors point out that very few additional facet-inducing inequalities are needed in order to obtain excellent lower bounds on the minimum tour length and in some cases to prove optimality as well.
- Facet identification for the symmetric traveling salesman polytope
- scientific article; zbMATH DE number 3943559
- A procedure of facet composition for the symmetric traveling salesman polytope
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- scientific article; zbMATH DE number 4083375
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Polyhedral results for a vehicle routing problem
- The traveling salesman problem: An overview of exact and approximate algorithms
- A cutting plane algorithm for the windy postman problem
- Resource constrained assignment problems
- A polyhedral approach to the rural postman problem
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Survey of facial results for the traveling salesman polytope
- Optimal solutions for the cutting stock problem
- Worst-case comparison of valid inequalities for the TSP
- Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
- The Steiner traveling salesman problem and its extensions
- On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
- The undirected \(m\)-capacitated peripatetic salesman problem
- Generating subtour elimination constraints for the TSP from pure integer solutions
- A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
- Continuous maximal covering location problems with interconnected facilities
- Facet generating techniques
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- Sinc Methods on Polyhedra
- scientific article; zbMATH DE number 5539506 (Why is no real title available?)
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- scientific article; zbMATH DE number 4083375 (Why is no real title available?)
- The facets of the asymmetric 5-city traveling salesman polytope
- scientific article; zbMATH DE number 91756 (Why is no real title available?)
- scientific article; zbMATH DE number 782052 (Why is no real title available?)
- Fast polyhedra abstract domain
- A new integer programming formulation of the graphical traveling salesman problem
- On 0-1 polytopes with many facets
- Rearrangement of DNA fragments: a branch-and-cut algorithm.
- Primal separation and approximation for the \(\{0,1/2\}\)-closure
- Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem
- Optimizing over the subtour polytope of the travelling salesman problem
- Solution of large-scale symmetric travelling salesman problems
- Mathematical programming formulations for machine scheduling: A survey
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- A projection method for the uncapacitated facility location problem
- Facet identification for the symmetric traveling salesman polytope
- Polarity and the complexity of the shooting experiment
- On the domino-parity inequalities for the STSP
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3714901)