一种基于牛顿法的约束最短路问题算法

An Algorithm Based on Newton Method for Constrained Shortest Path Problem

摘要: 针对通信网络中常见的信息传输路径规划问题，即约束最短路问题(Constrained Shortest Path, CSP)，由于该问题为NP-难问题，我们通过求解其拉格朗日对偶问题给出CSP问题的解。在求解对偶问题过程中，我们首先对于对偶问题的可行域进行限制，创新性地构造出了更紧的上界。其次，根据问题的特殊性，本文给出了求解对偶问题的新算法及牛顿迭代格式。其中每次迭代求解最短路问题，并通过所求的最短路径构造出对偶问题目标函数的梯度信息。此外我们采用超参数H来近似分段线性凸函数的二阶导数，从而构造出了牛顿迭代格式。新算法的数值实验表现出其求解CSP问题及其对偶问题的优势。

Abstract: Aiming at the information transmission path planning problem in communication networks, that is, the constrained shortest path problem, since the CSP problem is an NP-hard problem, we give the solution of the CSP problem by solving its Lagrange dual problem. In the process of solving the dual problem, we first limit the feasible fields of the dual problem and innovatively construct a tighter upper bound. Secondly, according to the particularity of the problem, a new algorithm for solving dual problems and Newtonian iteration format are given. Each iteration solves the shortest path problem, and constructs the gradient information of the objective function of the dual problem through the shortest path sought. In addition, we use the hyperparameter H to approximate the second derivative of the piecewise linear convex function, thus constructing the Newtonian iteration format. The numerical experiments of the new algorithm show its advantages in solving CSP problems and their duality problems.