一种求解QoS路由问题的半定规划算法

摘要

QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题.由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点.本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题.把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性.