A Network Design Problem with Two-Edge Matching Failures
Sharifov, Firdovsi1 ; Kutucu, Hakan2
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, 40 Prospekt Akademika Glushkova, 03187 Kiev, Ukraine.
2 Department of Computer Engineering, Karabuk University, 78050 Karabuk, Turkey
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 297-312.

In this paper, we introduce a network design problem with two-edge matching failures. Given a graph, any two edges non-incident to the same node form a two-edge matching. The problem consists in finding a minimum-cost subgraph such that, when deleting any two-edge matching of the graph, every pair of terminal nodes remains connected. We give mixed integer linear programming formulations for the problem and propose a heuristic algorithm based on the Branch-and-Bound method to solve it. We also present computational results.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014038
Classification : 68M10, 90C05, 90C27, 90B10
Mots-clés : Network design problem, linear programming, Branch-and-Bound method, matching
Sharifov, Firdovsi 1 ; Kutucu, Hakan 2

1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, 40 Prospekt Akademika Glushkova, 03187 Kiev, Ukraine.
2 Department of Computer Engineering, Karabuk University, 78050 Karabuk, Turkey 
@article{RO_2015__49_2_297_0,
     author = {Sharifov, Firdovsi and Kutucu, Hakan},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {A {Network} {Design} {Problem} with {Two-Edge} {Matching} {Failures}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {297--312},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014038},
     zbl = {1328.90020},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2014038/}
}
TY  - JOUR
AU  - Sharifov, Firdovsi
AU  - Kutucu, Hakan
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - A Network Design Problem with Two-Edge Matching Failures
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 297
EP  - 312
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2014038/
DO  - 10.1051/ro/2014038
LA  - en
ID  - RO_2015__49_2_297_0
ER  - 
%0 Journal Article
%A Sharifov, Firdovsi
%A Kutucu, Hakan
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T A Network Design Problem with Two-Edge Matching Failures
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 297-312
%V 49
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2014038/
%R 10.1051/ro/2014038
%G en
%F RO_2015__49_2_297_0
Sharifov, Firdovsi; Kutucu, Hakan. A Network Design Problem with Two-Edge Matching Failures. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 297-312. doi : 10.1051/ro/2014038. http://archive.numdam.org/articles/10.1051/ro/2014038/

M. Baïou, F. Barahona and A.R. Mahjoub, Separation of partition inequalities, Math. Oper. Res. 25 (2000) 243–254. | DOI | Zbl

F. Barahona, Network design using cut inequalities. SIAM. J. Optim. 6 (1996) 823–837. | DOI | Zbl

F.R.K. Chung and D. Mumford, Chordal completions of planar graphs. J. Comb. Theor. 31 (1994) 96–106. | DOI | Zbl

B. Fortz and M. Labbé, Polyhedral results for two-connected networks with bounded rings. Math. Program., Ser. A 93 (2002) 27–54. | DOI | Zbl

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

M. Grötschel, C.L. Monma and M. Stoer, Polyhedral and computational investigations for designing communication networks with high survivability requirements. Oper. Res. 43 (1995) 1012–1024. | DOI | Zbl

P. Haggernes, Minimal triangulation of graphs. A survey. Discrete Math. 306 (2008) 297–317. | DOI | Zbl

H. Kerivin and A.R. Mahjoub, Separation of partition inequalities for the (1,2) survivable network design problem. Oper. Res. Lett. 30 (2002) 265–268. | DOI | Zbl

H. Kerivin and A.R. Mahjoub, Design of Survivable Networks: A survey. Networks 46 (2005) 1–21. | DOI | Zbl

H. Kerivin and A.R. Mahjoub, On Survivable Network Polyhedra. Discrete Math. 290 (2005) 183–210. | DOI | Zbl

S. Kini, S. Ramasubramanian and A. Kvalbein, A. Hensen, Fast recovery from dual -link failures in IP networks using tunneling. IEEE/ACM Trans. Netw. 18:6 (2010) 1988–1999. | DOI

S.S. Lumetta and M. Médard, Classification of two-link failures for all-optical networks, In Proceedings of the Optical Fiber Communication Conference, California (2001).

A.R. Mahjoub, Two-edge connected spanning subgraphs and polyhedra. Math. Program. 64 (1994) 199–208. | DOI | Zbl

C.L. Monma and D.F. Shallcross, Methods for designing communications networks with certain two-connected survivability constraints. Oper. Res. 3 (1989) 531–541. | DOI

J.W. Morris Jr., Survey of materials science, I. Structure, Department of Materials Science and Engineering, University of California, Berkeley (2007) 138.

F.A. Sharifov, Reliable network design problem. Cybern. Syst. Anal. 4 (2000) 145–156. | Zbl

L.W. Wang, L. Zhang and K. Lu, Vacancy-decomposition-induced lattice instability and its correlation with the kinetic stability limit of crystal, Philosophical Magazine Lett. 85 (2005) 213–219. | DOI

B. Wu, K.L. Yeung and P.H. Ho, Monitoring cycle design for fast link failure location in all-optical networks. J. Lightwave Technol. 27 (2009) 1392–1401. | DOI

Cité par Sources :