The Steiner Traveling Salesman Polytope and Related Polyhedra
Baïou, Mourad; Mahjoub, Ali Ridha (2002), The Steiner Traveling Salesman Polytope and Related Polyhedra, SIAM Journal on Optimization, 13, 2, p. 498-507. http://dx.doi.org/10.1137/S1052623400322287
Type
Article accepté pour publication ou publiéDate
2002Journal name
SIAM Journal on OptimizationVolume
13Number
2Publisher
SIAM
Pages
498-507
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper 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.Subjects / Keywords
Polyhedral combinatorics; Polytopes; Traveling salesman problemRelated items
Showing items related by title and author.
-
Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Barahona, Francisco; Baïou, Mourad (2011) Chapitre d'ouvrage
-
Baïou, Mourad; Barahona, Francisco; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
-
Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
-
Bouchakour, Mustapha; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié