On the Steiner 2-edge connected subgraph polytope
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 259-283.

In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-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 2-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 3-edge cutsets. And we show that the generalized Steiner F-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 2-edge connected subgraph problem in that class of graphs.

DOI : 10.1051/ro:2008022
Classification : 05C85, 90C27
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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.1051/ro:2008022/

[1] M. Baïou, Le problème du sous-graphe Steiner 2-arête connexe: approche polyédrale. Ph.D. thesis, Université de Rennes 1 (1996).

[2] M. Baïou, F. Barahona and A.R. Mahjoub, Separation of partition inequalities. Math. Oper. Res. 25 (2000) 243-254. | MR | Zbl

[3] M. Baïou and A.R. Mahjoub, Steiner 2-edge connected subgraph polytopes on series-parallel graphs. SIAM J. Discrete Math. 10 (1997) 505-514. | MR | Zbl

[4] F. Barahona and A.R. Mahjoub, On two-connected subgraph polytopes. Discrete Math. 147 (1995) 19-34. | MR | Zbl

[5] D. Bienstock, E.F. Brickell and C.L. Monma, On the structure of minimum-weight k-connected spanning networks. SIAM J. Discrete Math. 3 (1990) 320-329. | MR | Zbl

[6] S.C. Boyd and T. Hao, An integer polytope related to the design of survivable communication networks. SIAM J. Discrete Math. 6 (1993) 612-630. | MR | Zbl

[7] S. Chopra, The k-edge connected spanning subgraph polyhedron. SIAM J. Discrete Math. 7 (1994) 245-259. | MR | Zbl

[8] N. Christofides and C.A. Whitlock, Network synthesis with connectivity constraints: a survey, in Operational Research 81, Hamburg edited by J.P. Brans (1981) 705-723. | Zbl

[9] G. Cornuéjols, J. Fonlupt and D. Naddef, The traveling salesman problem on a graph and some related integer polyhedra. Math. program. 33 (1985) 1-27. | MR | Zbl

[10] R. Coullard, A. Rais, R.L. Rardin and D.K. Wagner, Linear-time algorithm for the 2-connected Steiner subgraph problem on special classes of graphs. Networks 23 (1993) 195-206. | MR | Zbl

[11] R. Coullard, A. Rais, R.L. Rardin and D.K. Wagner, The dominant of the 2-connected steiner subgraph polytope for W4-free graphs. Discrete Appl. Math. 66 (1996) 33-43. | MR | Zbl

[12] M. Didi Biha and A.R. Mahjoub, k-edge connected polyhedra on series-parallel graphs. Oper. Res. Lett. 19 (1996) 71-78. | MR | Zbl

[13] M. Didi Biha and A.R. Mahjoub, The k-edge connected subgraph problem I: Polytopes and critical extreme points. Linear Algebra Appl. 381 (2004) 117-139. | MR | Zbl

[14] R.E. Erikson, C.L. Monma, and Jr. A.F. Veinott, Send and split method for a minimum-concave-cost network flows. Math. Oper. Res. 12 (1987) 634-664. | MR | Zbl

[15] J. Fonlupt and A.R. Mahjoub, 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] J. Fonlupt and A.R. Mahjoub, Critical extreme points of the 2-edge connected spanning subgraph polytope. Math. Program. 105 (2006) 289-310. | MR | Zbl

[17] J. Fonlupt and D. Naddef, The traveling salesman problem in graphs with some excluded minors. Math. Program. 53 (1992) 147-172. | MR | Zbl

[18] M. Grötschel and C. Monma, Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J. Discrete Math. 3 (1990) 502-523. | MR | Zbl

[19] M. Grötschel, C. Monma and M. Stoer, 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] M. Grötschel, C. Monma and M. Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res. 40 (1992) 309-330. | MR | Zbl

[21] M. Grötschel, C. Monma and M. Stoer, Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J. Optim. 2 (1992) 474-504. | MR | Zbl

[22] M. Grötschel, C.L. Monma and M. Stoer, 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] R. Halin, 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] H. Kerivin, Réseaux fiables et polyèdres. Ph.D. thesis, Université de Clermont Ferrand II, France (2000).

[25] H. Kerivin and A.R. Mahjoub, Design of survivable networks: A survey. Networks 46 (2005) 1-21. | MR | Zbl

[26] H. Kerivin, A.R. Mahjoub and C. Nocq, (1,2)-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] H. Kerivin and A. Ridha Mahjoub, On survivable network polyhedra. Discrete Math. 290 (2005) 183-210. | MR | Zbl

[28] A.R. Mahjoub, Two-edge connected spanning subgraphs and polyhedra. Math. Program. 64 (1994) 199-208. | MR | Zbl

[29] A.R. Mahjoub and P. Pesneau, On the Steiner 2-edge connected subgraph polytope. Technical Report RR-06:02, LIMOS, Université Blaise Pascal, Clermont-Ferrand, France (2006).

[30] C. Monma, B. Munson and W. Pulleyblank, Minimum-weight two-connected spanning networks. Math. Program. 46 (1990) 153-171. | MR | Zbl

[31] W.R. Pulleyblank, Polyhedral Combinatorics, OR & MS, in Optimization, volume 1, North Holland, Amsterdam (1989) 371-446. | MR

[32] K. Steiglitz, P. Weinen and D.J. Kleitmann, The design of minimum cost survivable networks. IEEE Trans. Circuit Theory 16 (1969) 455-460. | MR

[33] S. Voss, Steiner-probleme in graphen. Math. Systems in Economics (1990). | MR | Zbl

[34] P. Winter, Generalized Steiner problem in Halin graphs, in Proceedings of the 12th International Symposium on Math. Program. MIT (1985).

[35] P. Winter, Generalized Steiner problem in series-parallel networks. J. Algor. 7 (1986) 549-566. | MR | Zbl

Cité par Sources :