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

发布时间：2018-05-14 11:25

  本文选题：QoS路由 + 多约束路径(MCP)　； 参考：《系统工程理论与实践》2013年04期

【摘要】：QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优.该问题是一个NP-完全问题.提出了一种新的基于整数线性规划模型选择路由的方法.思路是将复杂约束引入到目标函数作为罚项,得到一个松弛整数线性规划问题.因为约束系数矩阵是全幺模矩阵,松弛问题可以通过线性规划很快地求解.拉格朗日乘子的调整用罚函数的方法很容易计算.数值实验表明提出的方法是有效的.
[Abstract]:The task of QoS routing is to find a path in the network that meets multiple constraints to optimize the utilization of network resources. This problem is a NP- complete problem. A new routing method based on integer linear programming model is proposed. The idea is to introduce complex constraints into the objective function as penalty terms and obtain a relaxed integer linear programming problem. Because the constraint coefficient matrix is a unimodular matrix, the relaxation problem can be solved quickly by linear programming. The adjustment of Lagrange multiplier is easy to calculate by the method of penalty function. Numerical experiments show that the proposed method is effective.
【作者单位】： 中国人民解放军理工大学通信工程学院;中国人民解放军68215部队;中国人民解放军西安通信学院;
【基金】：国家自然科学基金(70971136)
【分类号】：TP393.09;O221.4

【共引文献】

相关期刊论文 前1条

1 史长琼;黄辉;王大卫;张大方;;基于改进遗传算法的QoS路由优化[J];计算机工程与设计;2009年07期

相关博士学位论文 前1条

1 金劲;群集智能算法在网络策略中的研究及其应用[D];兰州理工大学;2011年

相关硕士学位论文 前3条

1 胡慧锋;无线电力数据采集系统的研究[D];浙江大学;2006年

2 杨海平;分布式系统数据邮递技术[D];长春理工大学;2010年

3 张子青;WSN中QoS保障下的动态路由配置算法设计与实现[D];东北大学;2011年

【二级参考文献】

相关期刊论文 前1条

1 王新红,王光兴;基于遗传算法的时延受限代价最小组播路由选择方法[J];通信学报;2002年03期

【相似文献】

相关期刊论文 前10条

1 吴文江;;大规模整数规划的分解方法[J];运筹学学报;1991年01期

2 吴少华，，朱伟，沈雷;批量计划问题的一类非线性整数规划模型研究[J];上海交通大学学报;1995年S1期

3 李玉娥,胡海波,付大庆;整数规划的一个解法[J];大庆高等专科学校学报;1996年04期

4 徐大申,邱启荣,何凤霞,彭武安;求解整数规划方法新探[J];华北电力大学学报;2004年05期

5 钟培华,孙小玲;凹整数规划的分枝定界解法(英文)[J];运筹学学报;2005年01期

6 雍龙泉;;基于整数规划的选课模型[J];伊犁师范学院学报;2006年03期

7 钟海林;叶祥企;;背包问题的若干性质及问题的简化[J];江西科学;2008年01期

8 李椿萱 ,周宁;定常不可压绕流的罚函数有限元计算[J];北京航空航天大学学报;1987年04期

9 刘富;;压缩式橡胶封隔件罚函数有限元分析[J];新疆石油科技;1993年01期

10 孙会霞;改进的非线性整数规划算法(英文)[J];数学季刊;2002年03期

相关会议论文 前10条

1 高玉波;;规划技术在关联项目选择中的应用[A];发展的信息技术对管理的挑战——99’管理科学学术会议专辑（上）[C];1999年

2 范体军;李宏宇;刘丽萍;;基于多目标混合整数规划的采购计划研究[A];中国优选法统筹法与经济数学研究会第七届全国会员代表大会暨第七届中国管理科学学术年会论文集[C];2005年

3 滕春贤;李磊;田广悦;李皓白;;一类非线性两级整数规划问题的全局优化方法[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

4 高玉波;;利用规划技术进行招标项目管理[A];2000中国控制与决策学术年会论文集[C];2000年

5 安向龙;李露凌;刘则毅;;基于杂合遗传算法的Portfolio整数规划模型[A];管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议暨中国科协第4届青年学术年会卫星会议论文集[C];2001年

6 高海云;朱文兴;;非线性混合整数规划的一类非光滑连续化方法[A];中国运筹学会第八届学术交流会论文集[C];2006年

7 刘志勇;滕春贤;陈东彦;;二层价格控制问题的研究[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

8 陈伟;张连生;;整数二次规划的全局最优性条件(英文)[A];中国运筹学会第八届学术交流会论文集[C];2006年

9 罗小明;刘克;刘宝碇;;前言[A];第四届中国青年运筹与管理学者大会论文集[C];2001年

10 江厚元;;运筹学实践的一些近期进展[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

相关博士学位论文 前10条

1 白富生;非线性规划中的精确罚函数[D];上海大学;2003年

2 冀淑慧;基于SDP松弛的整数规划凸化方法研究[D];复旦大学;2012年

3 陈伟;0-1二次规划的全局最优性条件及算法[D];上海大学;2005年

4 王继强;若干NP-困难的组合最优化问题的近似算法[D];山东大学;2008年

5 郑小金;连续和整数非凸二次规划理论和方法研究[D];上海大学;2010年

6 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年

7 潘少华;拉格朗日正则化方法与线性规划原—对偶算法的研究[D];大连理工大学;2002年

8 唐春明;强次可行方法与序列二次约束二次规划算法的研究[D];上海大学;2008年

9 贺素香;非线性优化中的一类对偶算法的理论研究[D];大连理工大学;2002年

10 达林;切平面在混合整数非线性规划中的应用[D];北京交通大学;2009年

相关硕士学位论文 前10条

1 彭凤;整数规划算法效率的研究[D];中南大学;2010年

2 刘淑芹;不等式约束的一种修改的罚函数方法[D];北京工业大学;2003年

3 赵亮;公用工程系统能量综合与优化设计方法研究[D];大连理工大学;2004年

4 熊鹰;微粒群算法的若干改进及应用[D];武汉理工大学;2006年

5 张昊;遗传算法在再制造逆向物流网络选址模型中的应用[D];吉林大学;2008年

6 武金瑛;遗传算法及其在结构优化中的应用[D];大连理工大学;2000年

7 贾超华;抛物系统的参数识别问题[D];华中师范大学;2002年

8 张立溥;整数线性规划中有效不等式与割平面研究[D];湘潭大学;2004年

9 李勇;近似算法在排样优化中的应用[D];华中科技大学;2005年

10 赵洋;席位分配及课堂点名模型的研究[D];西北工业大学;2006年

本文编号：1887666