求不相交QoS路由的一种整数线性规划方法

Integer linear program method of finding link - disjoint paths for QoS routing

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.

An integer linear program method is developed to deal with the problem of finding link-disjoint paths for QoS routing. Firstly, a set of 0-1 variables is given to model link-disjoint paths and QoS constraints. Then the complicating constraints are included in the objective function of the integer linear program problem formulated by Lagrangian multipliers. The integer linear program problem can be solved rapidly by using simplex algorithm for the totally unimodular of the constraint matrix. Furthermore link-disjoint paths for QoS routing can be found in the iterate process of solving linear program problems. Numerical experiment results show the effectiveness of the proposed method.