A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem

Abstract

Finding a routing path that satisfies two independent additive constraints (e.g., delay and cost) is a critical requirement in quality of service (QoS) routing. While this two-constraint path problem is NP-Hard, it is prevalent in practical network applications. Existing solutions typically face a trade-off: heuristics lack feasibility guarantees, while exact algorithms suffer from exponential computational complexity. In this paper, we propose a dual-guided exact algorithm that effectively bridges the gap between the computational efficiency of Lagrangian relaxation and the optimality guarantees of combinatorial search. Our method first solves the Lagrangian dual problem to derive the optimal multiplier, which subsequently serves as the optimal aggregate coefficient to guide a heuristic A*-prune search. This hybrid mechanism allows the algorithm to efficiently prune the search space while guaranteeing the identification of a cost-efficient feasible solution. Numerical experiments on random network topologies demonstrate that the proposed algorithm significantly outperforms the standard A*-prune algorithm while maintaining exactness. Specifically, in networks with up to 500 nodes, our method reduces the execution time by orders of magnitude compared to traditional exact methods.