A method of integer linear program for QoS routing problem
YU Zhan-ke, HUANG Hua-jun, NI Ming-fang, WU Xin-rong, MA Rui
Systems Engineering - Theory & Practice ›› 2013, Vol. 33 ›› Issue (4) : 1019-1023.
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.
QoS routing / multi-constrained path (MCP) / multi-constrained optimal path (MCOP) / integer programming / penalty function / totally unimodular matrix {{custom_keyword}} /
[1] Korkmaz T, Krunz M. Multi-constrained optimal path selection[C]// Proc INFOCOM 2001, Anchorage: IEEE, 2001: 834-843.
[2] Fei X, Luo J Z, Wu J Y, et al. QoS routing based on genetic algorithm[J]. Computer Communications, 1999, 22(15-16): 1392-1399.
[3] 米志超, 汪泽焱, 倪明放, 等. 一种基于Hopfield神经网络的Adhoc网络QoS路由选择算法[J]. 解放军理工大学学报:自然科学版, 2003, 4(5): 11-15.Mi Z C, Wang Z Y, Ni M F, et al. QoS routing optimal algorithm in Adhoc networks based on a new Hopfield neural network[J]. Journal of PLA University of Science and Technology: Natural Science Edition, 2003, 4(5): 11-15.
[4] 吴传信, 倪明放, 陈鸣. 路由选择的一种新遗传算法[J]. 电子科技大学学报, 2006, 35(5): 744-747.Wu C X, Ni M F, Chen M. A novel genetic algorithm for routing[J]. Journal of University of Electronic Science and Technology of China, 2006, 35(5): 744-747.
[5] Chen S, Nahrstedt K. On finding multi-constrained paths[C]// Proc ICC 1998, Atlanta: IEEE, 1998: 874-879.
[6] Van Mieghem P, Kuipers F A. On the complexity of QoS routing[J]. Computer Communications, 2003, 26(4): 376-387.
[7] Yuan X, Liu X. Heuristic algorithms for multi-constrained quality of service routing[C]// Twentieth Annual Joint of the IEEE Computer and Communications Societies, Anchorage, USA: IEEE, 2001: 844-853.
[8] Hassin R. Approximation schemes for the restricted shortest path problem[J]. Mathematics of Operations Research, 1992, 17(1): 36-42.
[9] Warburton A. Approximation of Pareto optimal in multiple objective shortest path problems[J]. Operations Research, 1987, 35(1): 70-79.
[10] Lorenz D H, Orda A, Raz D. Efficient QoS partition and routing of unicast and multicast[C]// Proc IWQoS 2000, Pittsburgh, USA: IEEE, 2000: 1336-1347.
[11] Carlyle W M, Royset J O, Kevin Wood R. Lagrangian relaxation and enumeration for solving constrained shortest-path problems[J]. Networks, 2008, 52(4): 256-270.
[12] Son T A, An L, Khadraoui D, et al. Solving QoS routing problems by DCA[J]. Intelligent Information and Database Systems, 2010, 5991: 460-470.
[13] Fumero F. A modified subgradient algorithm for Lagrangian relaxation[J]. Computers & Operations Research, 2001, 28(1): 33-52.
[14] Horst R, Pardalos P M, Thoai N V. 全局最优化引论[M]. 黄选红,译. 北京: 清华大学出版社, 2003.Horst R, Pardalos P M, Thoai N V. Introduction to global optimization[M]. Beijing: Tsinghua University Press, 2003.
[15] Nemhauser G L, Wolsey L A. Integer and combinatorial optimization[M]. New York: John Willey and Sons, 1988: 540-546.
[16] Nocedal J, Wright S J. Numerical optimization[M]. New York: Springer, 1999.
/
〈 | 〉 |