Bisection and Exact Algorithms Based on the Lagrangian Dual for a Single-Constrained Shortest Path Problem

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 Juttner 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.