×

The Steiner traveling salesman polytope and related polyhedra. (English) Zbl 1013.05071

Summary: We consider an extended formulation of the Steiner traveling salesman problem, that is, when variables are associated with both the edges and the nodes of the graph. We give a complete linear description of the associated polytope when the underlying graph is series-parallel. By projecting this polytope onto the edge variables, we obtain a characterization of the Steiner traveling salesman polytope in the same class of graphs. Both descriptions yield polynomial time (cutting plane) algorithms for the corresponding problems in that class of graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI