摘要
具有非线性参数的QoS路由分为含有非线性约束条件的QoS路由和含有非线性优化目标的QoS路由两类,它们都是NP问题.提出了两种启发式算法求解这两类QoS路由优化问题问题.对第一类问题,求解去掉非线性约束条件后的优化问题.如果找到的解满足非线性约束条件,则该解是最优解;否则在优化问题中添加一个新的线性约束,将已得到的解去掉,反复下去就可得到最终解.对第二类问题,将非线性优化目标换为约束条件中的线性参数,求解此优化模型,如果有解,则记录此时对应的非线性目标值.而后增加一个新的线性约束,去掉刚才得到的解,比较两次得到的非线性目标值,保留最小值.如果得到的解不满足该线性参数的约束条件,则算法结束;否则继续迭代.证明了两种算法的收敛性,并且时间复杂性为近似多项式时间.计算实例表明了算法的有效性.
QoS route with nonlinear parameters can be divided two kinds. One is route with nonlinear constraint; the other is route with nonlinear objective. Two heuristic algorithms are presented to solve these two kinds of problems. The first algorithm solves the optimization problem without nonlinear constraint. If the solution can satisfy the nonlinear constraint then algorithm stops with optimization path can be solved. Otherwise a new linear constraint can be added, which aim is to eliminate the path to be found, and to solve the new optimization problem with linear constraints. The second algorithm solves the optimization problem with linear constraint as objective instead of the nonlinear objective. If the problem has the solution then add a new linear constraint, which aim is to eliminate the selected path. Then compare the two nonlinear objective＇s value and save the minimum. If the problem has no feasible solution then algorithm stops. The two algorithms are proved to be convergent and have approximate polynomial time. Finally the examples demonstrate the validity of two algorithms.
出处
《小型微型计算机系统》
CSCD
北大核心
2006年第10期1837-1841,共5页
Journal of Chinese Computer Systems
关键词
OoS路由
非线性参数
启发式算法
整数规划
最优解
QoS route
nonlinear parameter
heuristic algorithm
integer programming
optimization
