A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem
International Journal of Foundations of Computer Science · 16.07.2026 · 1-14
DOI: 10.1142/s0129054126430033 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 16.07.2026. Verfasst von Kaixiang Hu und 2 weiteren Autor:innen. Gefördert von: Beijing Natural Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- Beijing Natural Science Foundation
Zitieren
APA
Hu, K., Li, X., & Kou, C. (2026). A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem. International Journal of Foundations of Computer Science, 1-14. https://doi.org/10.1142/s0129054126430033
Vancouver
Hu K, Li X, Kou C. A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem. International Journal of Foundations of Computer Science. 2026:1-14. doi:10.1142/s0129054126430033
BibTeX
@article{Hu2026,
author = {Hu, Kaixiang and Li, Xiankai and Kou, Caixia},
title = {A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--14},
doi = {10.1142/s0129054126430033}
}
EUVIMED