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

A method of integer linear program for QoS routing problem

作　　者：于战科[1] 黄华军[2] 倪明放[1] 武欣嵘[1] 马瑞[3] 

机构地区：[1]中国人民解放军理工大学通信工程学院 [2]中国人民解放军68215部队 [3]中国人民解放军西安通信学院

出　　处：《系统工程理论与实践》2013年第4期1019-1023,共5页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70971136)

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

关 键 词：QOS路由 多约束路径(MCP) 多约束优化路径(MCOP) 整数规划 罚函数 全幺模矩阵 

分 类 号：TN913.11[电子电信—通信与信息系统]