Geodesic
Tabu search for the discrete $(r|p)$-centroid problem
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 19-40

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2012_19_2_a1,
     author = {I. A. Davydov},
     title = {Tabu search for the discrete $(r|p)$-centroid problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {19--40},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_2_a1/}
}
TY  - JOUR
AU  - I. A. Davydov
TI  - Tabu search for the discrete $(r|p)$-centroid problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 19
EP  - 40
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_2_a1/
LA  - ru
ID  - DA_2012_19_2_a1
ER  - 
%0 Journal Article
%A I. A. Davydov
%T Tabu search for the discrete $(r|p)$-centroid problem
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 19-40
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_2_a1/
%G ru
%F DA_2012_19_2_a1
I. A. Davydov. Tabu search for the discrete $(r|p)$-centroid problem. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 19-40. http://geodesic.mathdoc.fr/item/DA_2012_19_2_a1/