求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.

A method of integer linear program for QoS routing problem

The task of quality of service (QoS) routing is to find a route in the network that satisfies a set of constraints while maintaining high utilization of network resources. It is well-known that this problem is NP-complete. In this paper, a new method of integer linear program model for QoS routing problem was proposed. The idea is to include complicating constraints in the objective function with the "penalty" term, and then obtain the Lagrangian relaxation integer linear problem. For the constraint matrix is totally unimodular, the relaxation can be solved rapidly from a linear program. Updating of Lagrangian multipliers are calculated easily by penalty function method. Numerical computational results indicate that the proposed method is effect.