Optimization algorithms for resilient path selection in networks. (English) Zbl 07350575

Casazza, Marco; Ceselli, Alberto

Comput. Oper. Res. 128, Article ID 105191, 13 p. (2021).

Summary: We study a Resilient Path Selection Problem (RPSP) arising in the design of communication networks with reliability guarantees. A graph is given, in which every arc has a cost and a probability of failure, and in which two nodes are marked as source and destination. The aim of our RPSP is to find a subgraph of minimum cost, containing a set of paths from the source to the destination nodes, such that the probability that all paths fail simultaneously is lower than a given threshold. We explore its theoretical properties and show that, despite a few interesting special cases can be solved in polynomial time, it is in general NP-hard. In fact, we prove that even deciding if a given subgraph has a probability of failure not exceeding a given threshold is already NP-Complete. We therefore introduce an integer relaxation that simplifies the computation of such probability, and we design an exact algorithm for the full RPSP exploiting this relaxation and other ad hoc procedures. We present computational results, highlighting that our exact algorithms can handle graphs with up to 30 nodes within minutes of computing time, consistently producing proven optimal solutions. Moreover, we show that our algorithms can be used also as heuristics, outperforming path protection schemes from the literature also on much larger networks.

MSC:

90B18	Communication networks in operations research
90B10	Deterministic network models in operations research
90B25	Reliability, availability, maintenance, inspection in operations research
90B80	Discrete location and assignment

Keywords:

network reliability; failure probability; path selection; column generation; branch and price

Software:

CPLEX; SCIP; aGrUM

References:

[1]	Achterberg, T., Scip: solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41 (2009) · Zbl 1171.90476
[2]	Andreas, A.; Smith, J.; Küçükyavuz, S., Branch-and-price-and-cut algorithms for solving the reliable h-paths problem, J. Global Optim., 42, 443-466 (2008) · Zbl 1159.90012
[3]	Barrera, J.; Cancela, H.; Moreno, E., Topological optimization of reliable networks under dependent failures, Oper. Res. Lett., 43, 2, 132-136 (2015) · Zbl 1408.90048
[4]	Berman, O.; Krass, D.; Menezes, M. B.C., Facility reliability issues in network p-median problems: strategic centralization and co-location effects, Oper. Res., 55, 2, 332-350 (2007) · Zbl 1167.90466
[5]	Boros, E.; Scozzari, A.; Tardella, F.; Veneziani, P., Polynomially computable bounds for the probability of the union of events, Math. Oper. Res., 39, 4, 1311-1329 (2014) · Zbl 1314.60033
[6]	Canale, E., Cancela, H., Robledo, F., Romero, P., Sartor, P. Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior. Networks 66(4). · Zbl 1386.05182
[7]	Casazza, M., Ceselli, A., Taverna, A., 2018. Mathematical formulations for the optimal design of resilient shortest paths. In: New Trends in Emerging Complex Real Life Problems, Proceedings of AIRO 2018.
[8]	Ceselli, A.; Righini, G.; Tresoldi, E., Combined location and routing problems for drug distribution, Discrete Appl. Math., 130-145 (2014) · Zbl 1295.90016
[9]	Cheng, J.; Lisser, A., Maximum probability shortest path problem, Discrete Appl. Math., 192, 40-48 (2015), 11th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012) · Zbl 1319.05078
[10]	CPLEX development team, IBM Ilog CPLEX Optimization Studio: CPLEX User’s Manual - Version 12 Release 6 (2011), IBM corp, (Tech. rep.)
[11]	Gonzales, C., Torti, L., Wuillemin, P.-H., 2017. aGrUM: a Graphical Universal Model framework. In: International Conference on Industrial Engineering, Other Applications of Applied Intelligent Systems, Proceedings of the 30th International Conference on Industrial Engineering, Other Applications of Applied Intelligent Systems, Arras, France.
[12]	Gonzalez-Montoro, N.; Cherini, R.; Finochietto, J. M., A multiple-link failures enumeration approach for availability analysis on partially disjoint paths, (13th International Conference on the Design of Reliable Communication Networks (DRCN) (2017))
[13]	Jan, Rong-Hong; Hwang, Fung-Jen; Chen, Sheng-Tzong, Topological optimization of a communication network subject to a reliability constraint, IEEE Trans. Reliab., 42, 1, 63-70 (1993) · Zbl 0775.90163
[14]	Kerivin, H.; Mahjoub, A. R., Design of survivable networks: a survey, Networks, 46, 1, 1-21 (2005) · Zbl 1072.90003
[15]	Koh, S. J.; Lee, C. Y., A tabu search for the survivable fiber optic communication network design, Comput. Ind. Eng., 28, 4, 689-700 (1995)
[16]	Konak, A.; Smith, A. E., Network Reliability Optimization, 735-760 (2006), Springer US: Springer US Boston, MA · Zbl 1118.90016
[17]	Pioro, M., Medhi, D., 2004. Routing, Flow, and Capacity Design in Communication and Computer Networks, The Morgan Kaufmann Series in Networking. Elsevier Science. · Zbl 1069.68021
[18]	Preékopa, A., 2003. Stochastic Programming, Elsevier B.V. Ch. Probabilistic Programming. pp. 267-351.
[19]	Puerto, J.; Ricca, F.; Scozzari, A., Reliability problems in multiple path-shaped facility location on networks, Discrete Optim., 12, 61-72 (2014) · Zbl 1308.90091
[20]	Redmond, M.; Campbell, A.; Ehmke, J., The most reliable flight itinerary problem, Networks, 73, 3, 325-343 (2019), cited By 1
[21]	Robledo, F.; Romero, P.; Saravia, M., On the interplay between topological network design and diameter constrained reliability, (12th International Conference on the Design of Reliable Communication Networks (DRCN) (2016))
[22]	Shen, Z.-J. M.; Zhan, R. L.; Zhang, J., The reliable facility location problem: formulations, heuristics, and approximation algorithms, INFORMS J. Comput., 23, 3, 470-482 (2011) · Zbl 1243.90096
[23]	Snyder, L. V.; Daskin, M. S., Reliability models for facility location: the expected failure cost case, Transp. Sci., 39, 3, 400-416 (2005)
[24]	Song, Y.; Luedtke, J., Branch-and-cut approaches for chance-constrained formulations of reliable network design problems, Math. Programm. Comput., 5, 397-432 (2013) · Zbl 1330.90057
[25]	Weber, P., Jouffe, L., 2006. Complex system reliability modelling with dynamic object oriented bayesian networks (doobn). Reliab. Eng. Syst. Saf. 91(2), 149-162. selected Papers Presented at QUALITA 2003.