GPS–SP: Generative Problem Solver for the Shortest Path Problem
Chengheng Lyu, Hsiang-Shun Shih, Phillip C.‐Y. Sheu · International Journal of Semantic Computing · 2026
Finding shortest paths in graphs with complex constraints is a fundamental problem in optimization with applications ranging from network routing to robotics. Traditional approaches either rely on exhaustive enumeration, which has exponential complexity, or generic constraint solvers that fail to exploit the problem structure. We present a constraint-aware optimization framework Generative Problem Solver for the Shortest Path Problem (GPS-SP) that categorizes constraints by their computational properties and applies specialized algorithms to each category. Our framework enables automatic problem generation and constraint composition, thereby forming a generative problem solver for shortest path problems. It supports five constraint categories: (A) hard filters for static graph filtering, (B) regular constraints expressible as finite automata, (C) budget constraints on accumulated resources, (D) global graph properties, and (E) combinatorial constraints. We prove the completeness and optimality of our approach for all category combinations and demonstrate a [Formula: see text] average speedup ([Formula: see text] median) over exhaustive search on 1500 benchmark problems and a [Formula: see text] average speedup ([Formula: see text] median) over GPT-5.2 on 1280 benchmark problems with 54.2% agreement rate. This work provides both theoretical guarantees and practical efficiency for constraint shortest path problems and demonstrates a blueprint for extending the framework to other combinatorial optimization domains.