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

      0 references
      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references