No label defined (Q3714901)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3943560
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3943560 |
Statements
1985
0 references
survey
0 references
computational aspects
0 references
polyhedral theory
0 references
traveling salesman
0 references
facet-including linear inequalities
0 references
cutting plane algorithm
0 references
ellipsoid algorithm
0 references
subtour elimination
0 references
clique tree inequalities
0 references
Heuristic
0 references
polynomial algorithm
0 references
relaxation method
0 references
0.8972253203392029
0 references
0.8222490549087524
0 references
0.816351056098938
0 references
[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.
0 references