In this paper, we study the Steiner -edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner -partition inequalities, that generalizes the so-called Steiner -partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner -edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by -edge cutsets. And we show that the generalized Steiner -partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner -edge connected subgraph problem in that class of graphs.
Mots-clés : polytope, Steiner $2$-edge connected graph, Halin graph
@article{RO_2008__42_3_259_0,
author = {Mahjoub, A. Rhida and Pesneau, Pierre},
title = {On the {Steiner} $2$-edge connected subgraph polytope},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {259--283},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008022},
mrnumber = {2444486},
zbl = {1157.05049},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2008022/}
}
TY - JOUR AU - Mahjoub, A. Rhida AU - Pesneau, Pierre TI - On the Steiner $2$-edge connected subgraph polytope JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 259 EP - 283 VL - 42 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2008022/ DO - 10.1051/ro:2008022 LA - en ID - RO_2008__42_3_259_0 ER -
%0 Journal Article %A Mahjoub, A. Rhida %A Pesneau, Pierre %T On the Steiner $2$-edge connected subgraph polytope %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 259-283 %V 42 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2008022/ %R 10.1051/ro:2008022 %G en %F RO_2008__42_3_259_0
Mahjoub, A. Rhida; Pesneau, Pierre. On the Steiner $2$-edge connected subgraph polytope. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 259-283. doi : 10.1051/ro:2008022. http://www.numdam.org/articles/10.1051/ro:2008022/
[1] , Le problème du sous-graphe Steiner 2-arête connexe: approche polyédrale. Ph.D. thesis, Université de Rennes 1 (1996).
[2] , and , Separation of partition inequalities. Math. Oper. Res. 25 (2000) 243-254. | MR | Zbl
[3] and , Steiner 2-edge connected subgraph polytopes on series-parallel graphs. SIAM J. Discrete Math. 10 (1997) 505-514. | MR | Zbl
[4] and , On two-connected subgraph polytopes. Discrete Math. 147 (1995) 19-34. | MR | Zbl
[5] , and , On the structure of minimum-weight -connected spanning networks. SIAM J. Discrete Math. 3 (1990) 320-329. | MR | Zbl
[6] and , An integer polytope related to the design of survivable communication networks. SIAM J. Discrete Math. 6 (1993) 612-630. | MR | Zbl
[7] , The -edge connected spanning subgraph polyhedron. SIAM J. Discrete Math. 7 (1994) 245-259. | MR | Zbl
[8] and , Network synthesis with connectivity constraints: a survey, in Operational Research 81, Hamburg edited by J.P. Brans (1981) 705-723. | Zbl
[9] , and , The traveling salesman problem on a graph and some related integer polyhedra. Math. program. 33 (1985) 1-27. | MR | Zbl
[10] , , and , Linear-time algorithm for the 2-connected Steiner subgraph problem on special classes of graphs. Networks 23 (1993) 195-206. | MR | Zbl
[11] , , and , The dominant of the 2-connected steiner subgraph polytope for -free graphs. Discrete Appl. Math. 66 (1996) 33-43. | MR | Zbl
[12] and , -edge connected polyhedra on series-parallel graphs. Oper. Res. Lett. 19 (1996) 71-78. | MR | Zbl
[13] and , The -edge connected subgraph problem I: Polytopes and critical extreme points. Linear Algebra Appl. 381 (2004) 117-139. | MR | Zbl
[14] , , and , Send and split method for a minimum-concave-cost network flows. Math. Oper. Res. 12 (1987) 634-664. | MR | Zbl
[15] and , Critical extreme points of the 2-edge connected subgraph polytope, in Integer Programming and Combinatorial Optimization: 7th International IPCO Conference, edited by G. Cornuéjols, R.E. Burkard and G.J. Woeginger, Lect. Notes Comput. Sci. Graz, Austria, Springer-Verlag 1610 (1999) 166-183. | MR | Zbl
[16] and , Critical extreme points of the 2-edge connected spanning subgraph polytope. Math. Program. 105 (2006) 289-310. | MR | Zbl
[17] and , The traveling salesman problem in graphs with some excluded minors. Math. Program. 53 (1992) 147-172. | MR | Zbl
[18] and , Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J. Discrete Math. 3 (1990) 502-523. | MR | Zbl
[19] , and , Polyhedral approaches to network survivability, in Reliability of computer and Communication Networks, edited by F. Hwang F. Roberts and C. Monma, Series Discrete Math. Comput. Sci. 5 (1991) 121-141 AMS/ACM. | MR | Zbl
[20] , and , Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res. 40 (1992) 309-330. | MR | Zbl
[21] , and , Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J. Optim. 2 (1992) 474-504. | MR | Zbl
[22] , and , Design of Survivable Networks, in Network Models, Handbooks in Operations Research and Management Science, Elsevier, North-Holland, Amsterdam, Vol. 7, chapter 10 (1995) 617-672. | MR | Zbl
[23] , Studies on minimality n-connected graphs. In Combinatorial Math. Appl., edited by J.A. Welsh, Academic Press, New York (1971) 129-136. | MR | Zbl
[24] , Réseaux fiables et polyèdres. Ph.D. thesis, Université de Clermont Ferrand II, France (2000).
[25] and , Design of survivable networks: A survey. Networks 46 (2005) 1-21. | MR | Zbl
[26] , and , -survivable networks: Facets and branch-and-cut, in The Sharpest Cut, edited by M. Grötschel, MPS-SIAM Series in Optimization (2004) 121-152. | MR | Zbl
[27] and , On survivable network polyhedra. Discrete Math. 290 (2005) 183-210. | MR | Zbl
[28] , Two-edge connected spanning subgraphs and polyhedra. Math. Program. 64 (1994) 199-208. | MR | Zbl
[29] and , On the Steiner 2-edge connected subgraph polytope. Technical Report RR-06:02, LIMOS, Université Blaise Pascal, Clermont-Ferrand, France (2006).
[30] , and , Minimum-weight two-connected spanning networks. Math. Program. 46 (1990) 153-171. | MR | Zbl
[31] , Polyhedral Combinatorics, OR & MS, in Optimization, volume 1, North Holland, Amsterdam (1989) 371-446. | MR
[32] , and , The design of minimum cost survivable networks. IEEE Trans. Circuit Theory 16 (1969) 455-460. | MR
[33] , Steiner-probleme in graphen. Math. Systems in Economics (1990). | MR | Zbl
[34] , Generalized Steiner problem in Halin graphs, in Proceedings of the 12th International Symposium on Math. Program. MIT (1985).
[35] , Generalized Steiner problem in series-parallel networks. J. Algor. 7 (1986) 549-566. | MR | Zbl
Cité par Sources :
