Distance confined path problem and separable integer programming

Abstract

We consider in this article a problem of finding paths in a graph within a distance window, termed distance-confined path problem and develop a successive graph reduction scheme to solve such a problem effectively. Integrated with the surrogate constraint formulation, our proposed solution algorithm for the distance-confined path problem finds a prominent application in separable non-linear integer programming. By forming a family of distance-confined path problems, we are able to remove gradually all primal infeasible points in the region defined by the surrogate constraint and eventually achieve an exact equivalence between the surrogate constraint formulation and the primal problem, thus a zero duality gap.

Keywords:

• kth shortest path problem
• graph reduction
• dynamic programming
• separable integer programming
• surrogate constraint formulation

AMS Subject Classifications::

• 90C09
• 90C10
• 90C30
• 65K05

Acknowledgements

This research was partially supported by the Research Grants Council, Hong Kong under Grants CUHK414207 and 2050478. The authors appreciate Mr. Baiyi Wu for his help in preparing the graphs in this article.