Volume 19, No 2, 2012, P. 19-40

UDC 510.53
I. A. Davydov 
Tabu search for the discrete (r|p)-centroid problem

Abstract:
We consider the discrete (r|p)-centroid problem and develop a probabilistic tabu search algorithm for it. It is shown that probability of finding global optima with this algorithm converges to one as number of iterations grows if proper restrictions for Tabu list size are satisfied. We use Lagrangian relaxations for evaluation of the goal function’s values. It is proved that this evaluation is not worse than linear program relaxation. Different methods of subgradient optimization are studied to solve the relaxed problem. The presented algorithm was tested on the benchmarks from the library “Discrete Location Problems”. Computational results show that the algorithm finds optimal solutions with high frequency.
Ill. 4, tab. 5, bibliogr. 21.

Keywords: competitive facility location, Stackelberg games, bilevel programming.

Davydov Ivan Aleksandrovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: iadavydov@math.nsc.ru