Mobile-edge computation edge servers (ESs) act as crucial intermediaries between mobile devices (MDs) and cloud computing centers, ensuring low-latency computation and reliable IoT network performance. However, regional failures induced by natural or man-made disasters can severely disrupt ES operations. This paper focuses on devising an effective repair scheme for ESs after large-scale disasters, particularly under the uncertainty of secondary disasters and the stochastic demands of MDs. We formulate the edge server repair problem (ESRP) as a mixed-integer linear programming (MILP) model and prove its NP-hardness. To effectively solve this problem, we propose a solution algorithm based on Benders decomposition (BD). The MILP problem is decomposed into a more solvable master problem and a series of subproblems, which are solved alternately and iteratively. Furthermore, we enhance our BD algorithm by incorporating two types of initial cuts to reduce the iterative number and accelerate the convergence speed. The first type is known as supermodular cut, which exploits the inherent properties of the problem. The second type is called aggregation capacity constraint, which exploits the capacity characteristics of ESs. Extensive simulation results demonstrate that the proposed method excels in ES repairing under large-scale IoT network failure scenarios. Compared to other available algorithms, our BD-based approach more efficiently achieves the exact solution to the ESRP, minimizing network demand loss within limited resources.

We propose two new algorithms called BiLAD and ExactBiLAD for the well-known Single-Constrained Shortest Path (SCSP) problem. It is a fundamental problem in quality-of-service (QoS) routing, where one seeks a source-destination path with the least cost satisfying a delay QoS constraint in a network. As pointed out by Jüttner et al., there is no widely accepted algorithm with polynomial time to the SCSP problem because the SCSP problem is NP-hard. The remarkable feature of BiLAD is that it ensures that the length of iteratively updated angle interval is shrunk at least at a constant ratio. With the help of this feature, we prove its polynomial time complexity. To the best of our knowledge, this is the first time that the polynomial time complexity is proved in details. The numerical results show that, in most QoS routing test instances, the performance of BiLAD is close to their primal optimal solutions. The proposed modified Dijkstra procedure, whose complexity is the same as that of the Dijkstra algorithm, also accelerates BiLAD. In the second part of the paper, based on the information obtained by BiLAD, we design an exact algorithm-ExactBiLAD, in which an optimal solution to the SCSP problem is finally obtained by scanning the steadily reduced optimal-path-candidate triangle area. The simulation results indicate that ExactBiLAD needs only a dozen times of executing the modified Dijkstra algorithm regardless of the network size or the average node degree. Distinguished from many other exact algorithms, ExactBiLAD has a satisfactory performance in the practical computation.