Simulated annealing and resource location in computer networks
G. “Anand” Anandalingam · 1989
This paper examines the problem of locating resources such as databases, controllers, and data processors on a computer network. The integer programming problem in location variables y and interconnection variables x is solved using two simulated annealing algorithms. Pure simulated annealing for this problem has complexity O(2N2+N). In hybrid simulated annealing (HSA), for fixed y, the problem in x becomes a special case of the transporation problem; the worst case solution for HSA is O(N.2N). In parallel simulated annealing (PSA), a decomposition procedure yields knapsack problems for x when y = 1, and x = 0 when y = 0; this is solved in O(Nk2N). Numerical results show that the computation time taken by the simulated annealing algorithms are comparable to a Lagrangian relaxation procedure, and the solutions are on the average within 8 % of a lower bound.