Heuristic Algorithm for QoS Route with Nonlinear Parameters
Xingchun Diao · Journal of Chinese Computer Systems · 2006
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.