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/

[1] Alekseeva E. V., Kochetova N. A., “Verkhnie i nizhnie granitsy dlya konkurentnoi zadachi o $p$-mediane”, Tr. XIV-i Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 1, RIO IDSTU SO RAN, Irkutsk, 2008, 563–569

[2] Goncharov E. N., Kochetov Yu. A., “Veroyatnostnyi poisk s zapretami dlya diskretnykh zadach bezuslovnoi optimizatsii”, Diskret. analiz i issled. operatsii. Ser. 2, 9:2 (2002), 13–30 | MR | Zbl

[3] Kochetov Yu. A., Paschenko M. G., Plyasunov A. V., “O slozhnosti lokalnogo poiska v zadache o $p$-mediane”, Diskret. analiz i issled. operatsii. Ser. 2, 12:2 (2005), 44–71 | MR | Zbl

[4] Alekseeva E., Kochetova N., Kochetov Yu., Plyasunov A., “A hybrid memetic algorithm for the competitive $p$-median problem”, Proc. INCOM (Moscow, Russia, June 3–5, 2009), ICS RAS Publ., Moscow, 2009, 1516–1520

[5] Alekseeva E., Kochetov Yu., Plyasunov A., “Complexity of local search for the $p$-median problem”, Eur. J. Oper. Res., 191 (2008), 736–752 | DOI | MR | Zbl

[6] Alekseeva E. V., Kochetova N. A., Kochetov Yu. A., Plyasunov A. V., “A heuristic and exact methods for the discrete $(r|p)$-centroid problem”, Evolutionary computation in combinatorial optimization, Proc. 10th Eur. Conf. EvoCOP 2010, Istanbul, Turkey, April 7–9, 2010, 6022, Springer-Verl., Berlin, 2010, 11–22

[7] Barahona F., Chudak F. A., “Near-optimal solutions to large-scale facility location problems”, Discrete Optimization, 2 (2005), 35–50 | DOI | MR | Zbl

[8] Benati S., Laporte G., “Tabu search algorithms for the ($r|X_p$)-medianoid and ($r|p$)-centroid problems”, Locat. Sci., 2:2 (1994), 193–204 | Zbl

[9] Bhadury J., Eiselt Y., Jaramillo J., “An alternating heuristic for medianoid and centroid problems in the plane”, Comput. Oper. Res., 30 (2003), 553–565 | DOI | MR | Zbl

[10] Drezner T., Eiselt H. A., “Consumers in competitive location models”, Facility location. Applications and theory, Springer-Verl., Berlin, 2004, 151–178 | MR

[11] Frangeoni A., “About Lagrangian methods in integer optimization”, Ann. Oper. Res., 139 (2005), 163–193 | DOI | MR

[12] Geoffrion A. M., “Lagrangian relaxation for integer programming”, Math. Program. Study Ser., 2 (1974), 82–114 | DOI | MR | Zbl

[13] Glover F., Laguna M., Tabu search, Kluwer Acad. Publ., Boston, 1997, 408 pp. | MR | Zbl

[14] Guinard M., “Lagrangian relaxation”, TOP, 11 (2003), 215–228 | DOI

[15] Hakimi S. L., “Locations with spatial interactions: competitive locations and games”, Discrete Locat. Theory, Wiley, New York, 1990, 439–478 | MR

[16] Held M., Wolfe P., Crowder H. P., “Validation of subgradient optimization”, Math. Program., 6:1 (1974), 62–88 | DOI | MR | Zbl

[17] Kochetov Yu., Kononov A., Plyasunov A., “Competitive facility location models”, Comput. Math. Math. Physics, 49:6 (2009), 994–1009 | DOI | MR | Zbl

[18] Lemaréchal C., “Lagrangian relaxation”, Computational combinatorial optimization, Springer-Verl., Heidelberg, 2001, 115–160 | MR

[19] Noltemeier H., Spoerhase J., Wirth H.-C., “Multiple voting location and single voting location on trees”, Eur. J. Oper. Res., 181 (2007), 654–667 | DOI | MR | Zbl

[20] Poljak B. T., “Subgradient methods: a survey of Soviet research”, Nonsmooth optimization, IIASA Proc. Ser., 3, 1977, 5–30 | MR

[21] Shor N. Z., Minimization methods for non-differentiable functions, Springer-Verl., New York, 1985, 162 pp. | MR