[en] We study the problem of designing at minimum cost a two-connected network such that each edge
belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with
bounded meshes problem studied by Fortz, Labb´e and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877,
2000).
In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem
is strongly NP-complete for any fixed K , and we derive a new class of facet defining inequalities. Numerical results
obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem.
Disciplines :
Méthodes quantitatives en économie & gestion
Auteur, co-auteur :
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Labbé, M.
Langue du document :
Anglais
Titre :
Two-Connected Networks with Rings of Bounded Cardinality
F. Barahona, "Separating from the dominant of the spanning tree polytope," Op. Research Letters, vol. 12, pp. 201-203, 1992.
C. Berge, Graphs and Hypergraphs. North-Holland: Amsterdam, 1973.
S.C. Boyd and T. Hao, "An integer polytope related to the design of survivable communication networks," SIAM J. Discrete Math. vol. 6, no. 4, pp. 612-630, 1993.
W.H. Cunningham, "Optimal attack and reinforcement of a network," Journal of ACM, vol. 32, pp. 549-561, 1985.
B. Fortz, Design of Survivable Networks with Bounded Rings, vol. 2 of Network Theory and Applications. Kluwer Academic Publishers, 2000.
B. Fortz and M. Labbé, "Facets for the polyhedron of two-connected networks with bounded rings," Technical Report IS-MG 99/17, Université Libre de Bruxelles, CP 210/01, B-1050 Bruxelles, Belgique, 1999. Available at http://smg.ulb.ac.be/Preprints/Fortz99_17. html.
B. Fortz and M. Labbé, "Polyhedral results for two-connected networks with bounded rings," Mathematical Programming, vol. 93, no. 1, pp. 27-54, 2002.
B. Fortz, M. Labbé, and F. Maffioli, "Solving the two-connected network with bounded meshes problem," Operations Research, vol. 48, no. 6, pp. 866-877, 2000.
B. Fortz, P. Soriano, and C. Wynants, "A tabu search algorithm for self-healing ring network design," Technical Report IS-MG 2000/15, Université Libre de Bruxelles, 2000. To appear in European Journal of Operational Research.
R.E. Gomory and T.C. Hu, "Multi-terminal network flows," SIAM J. Appl. Math., vol. 9, pp. 551-570, 1961.
M. Grötschel and C.L. Monma, "Integer polyhedra arising from certain design problems with connectivity constraints," SIAM J. Discrete Math., vol. 3, pp. 502-523, 1990.
M. Grötschel, C.L. Monma, and M. Stoer, "Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints," Operations Research, vol. 40, no. 2, pp. 309-330, 1992.
M. Grötschel, C.L. Monma, and M. Stoer, Design of Survivable Networks, vol. 7 on Network models of Handbooks in OR/MS, chap. 10, pp. 617-672. North-Holland, 1995.
C.L. Monma and D.F. Shallcross, "Methods for designing communications networks with certain two-connected survivability constraints," Operations Research, vol. 37, no. 4, pp. 531-541, 1989.
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1988.
K. Steiglitz, P. Weiner, and D.J. Kleitman, "The design of minimum-cost survivable networks," IEEE Transactions on Circuit Theory, vol. CT-16, pp. 455-460, 1969.
S. Thienel, ABACUS-A Branch-And-Cut System. PhD thesis, Universität zu Köln, 1995.
S. Thienel, ABACUS-A Branch-And-Cut System, Version 2.0, User's Guide and Reference Manual. Universität zu Köln, 1997.
