scientific article; zbMATH DE number 16722

MaRDI QIDQ3973408zbMATH OpenFDO

Authors Denis Naddef

Publication date 26 June 1992

zbMATH Keywords

clique-tree inequalitiescomb inequalitieshandlessubtour elimination inequalitiessymmetric traveling salesman polytopeteeth

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic network models in operations research (90B10) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

[For the entire collection see Zbl 0722.00003.] The author reviews all the known inequalities for the symmetric traveling salesman polytope that are defined on two underlying families of subsets of the nodes, called handles and teeth. These are the subtour elimination inequalities, the comb inequalities; the clique-tree inequalities; the path, wheelbarrow, and bicycle inequalities; the star and hyperstar inequalities; and the binested inequalities.

Recommendations

• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• The Symmetric Traveling Salesman Polytope Revisited
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• Ladders for Travelling Salesmen

Cited in

(3)

• The general routing polyhedron: A unifying framework
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• The Symmetric Traveling Salesman Polytope Revisited

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 Q3973408)