Computing Inefficiency of Service Networks under Random Failures

In this work, our focus is directed towards the examination of service networks in the context of random failures. Specifically, when presented with a service network graph and a parameter value denoted as f ∈ N, we presuppose the existence of an underlying probability distribution across the entirety of f-simultaneous links failure scenarios. Our primary objective lies in the computation of the probability associated with scenarios wherein the network utilization exceeds unity. The derived probability serves as a metric for assessing the inefficiency inherent in the service network. It is crucial to note that this computational task is classified as NP-Hard, given that determining even a single failure scenario resulting in network inefficiency falls within the NP-Hard complexity class. To quantify the network inefficiency, we propose an approach that leverages recently developed techniques from the field of optimization under uncertainty, and integer programming. Furthermore, we harness advancements in optimization solvers, in particular the Gurobi solver. Another outcome of our methodology is the ability to identify failure scenarios that render service networks inefficient, thereby causing network utilization to exceed one. This foreknowledge serves as a valuable tool in proactively designing more resilient networks. We also provide computational results to substantiate our findings.