Mladenović, Nenad; Kratica, Jozef; Kovačević-Vujčić, Vera; Čangalović, Mirjana Variable neighborhood search for metric dimension and minimal doubly resolving set problems. (English) Zbl 1253.90199 Eur. J. Oper. Res. 220, No. 2, 328-337 (2012). Summary: Two similar NP-hard optimization problems on graphs are considered: the metric dimension problem and the problem of determining a doubly resolving set with the minimum cardinality. Both are present in many diverse areas, including network discovery and verification, robot navigation, and chemistry. For each problem, a new mathematical programming formulation is proposed. For solving more realistic large-size instances, a variable neighborhood search based heuristic is designed. An extensive experimental comparison on five different types of instances indicates that the VNS approach consistently outperforms a genetic algorithm, the only existing heuristic in the literature designed for solving those problems. Cited in 13 Documents MSC: 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming 05C12 Distance in graphs 90C35 Programming involving graphs or networks Keywords:metaheuristics; combinatorial optimization; variable neighborhood search; metric dimension; minimal doubly resolving set Software:OR-Library PDFBibTeX XMLCite \textit{N. Mladenović} et al., Eur. J. Oper. Res. 220, No. 2, 328--337 (2012; Zbl 1253.90199) Full Text: DOI Online Encyclopedia of Integer Sequences: a(n) is the metric dimension of the n-dimensional hypercube. References: [1] Bailey, R.; Cameron, P., Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society, 43, 209-242 (2011) · Zbl 1220.05030 [2] Bailey, R., & Meagher, K., 2011. On the metric dimension of Grassmann graphs. Technical Report. arXiv:1010.4495.; Bailey, R., & Meagher, K., 2011. On the metric dimension of Grassmann graphs. Technical Report. arXiv:1010.4495. · Zbl 1286.05035 [3] Beasley, J., Or-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990) [4] Beerliova, Z.; Eberhard, F.; Erlebach, T.; Hall, A.; Hoffmann, M.; Mihalák, M.; Ram, L., Network discovery and verification, IEEE Journal on Selected Areas in Communications, 24, 2168-2181 (2006) [5] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I.; Puertas, M.; Seara, C.; Wood, D., On the metric dimension of cartesian products of graphs, SIAM Journal in Discrete Mathematics, 21, 423-441 (2007) · Zbl 1139.05314 [6] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I.; Puertas, M., On the metric dimension of infinite graphs, Electronic Notes in Discrete Mathematics, 35, 15-20 (2009) · Zbl 1268.05140 [7] Chappell, G.; Gimbel, J.; Hartman, C., Bounds on the metric and partition dimensions of a graph, Ars Combinatoria, 88, 349-366 (2008) · Zbl 1224.05133 [8] Chartrand, G.; Eroha, L.; Johnson, M.; Oellermann, O., Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105, 99-113 (2000) · Zbl 0958.05042 [9] Currie, J.; Oellerman, O., The metric dimension and metric independence of a graph, Journal of Combinatorial Mathematics and Combinatorial Computing, 39, 157-167 (2001) · Zbl 0986.05040 [10] Davidovic, T.; Hansen, P.; Mladenovic, N., Permutation based genetic, tabu and variable neighborhood search heuristics for multiprocessor scheduling with communication delays, Asia-Pacific Journal of Operational Research, 22, 297-326 (2005) · Zbl 1085.90020 [11] Fehr, M.; Gosselin, S.; Oellermann, O., The metric dimension of Cayley digraphs, Discrete Mathematics, 306, 31-41 (2006) · Zbl 1085.05034 [12] Garcia, S., Labbe, M., & Marin, A., in press. Solving large p-median problems with a radius formulation. Informs Journal on Computing. doi:10.1287/ijoc.1100.0418; Garcia, S., Labbe, M., & Marin, A., in press. Solving large p-median problems with a radius formulation. Informs Journal on Computing. doi:10.1287/ijoc.1100.0418 · Zbl 1243.90091 [13] Hansen, P.; Mladenović, N.; Moreno-Pérez, J., Variable neighbourhood search: methods and applications (invited survey), 4OR: A Quarterly Journal of Operations Research, 6, 319-360 (2008) · Zbl 1179.90332 [14] Hansen, P.; Mladenović, N.; Moreno-Pérez, J., Variable neighbourhood search: algorithms and applications, Annals of Operations Research, 175, 367-407 (2010) · Zbl 1185.90211 [15] Harary, F.; Melter, R., On the metric dimension of a graph, Ars Combinatoria, 2, 191-195 (1976) · Zbl 0349.05118 [16] Hauptmann, M.; Schmied, R.; Viehmann, C., On approximation complexity of metric dimension problem, Lecture Notes in Computer Science, 6460, 136-139 (2011) · Zbl 1326.68149 [17] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Cáceres, J.; Puertas, M., On the metric dimension of some families of graphs, Electronic Notes in Discrete Mathematics, 22, 129-133 (2005) · Zbl 1182.05050 [18] Hernando, C.; Mora, M.; Pelayo, I.; Seara, C.; Wood, D., Extremal graph theory for metric dimension and diameter, Electronic Notes in Discrete Mathematics, 29, 339-343 (2007) · Zbl 1341.05132 [19] Hernando, C.; Mora, M.; Pelayo, I.; Seara, C.; Wood, D., Extremal graph theory for metric dimension and diameter, Electronic Journal of Combinatorics, 17, 1-28 (2010) · Zbl 1219.05051 [20] Husnine, S.; Kousar, I., A subfamily of a generalized petersen graph p(n,3) with constant metric dimension, Utilitas Mathematica, 81, 111-120 (2010) · Zbl 1207.05045 [21] Ilić, A.; Urošević, D.; Brimberg, J.; Mladenović, N., A general variable neighborhood search for solving the uncapacitated single allocation p-Hub median problem, European Journal of Operational Research, 206, 289-300 (2010) · Zbl 1188.90142 [22] Imran, M.; Bokhary, S. U.H.; Baig, A., On families of convex polytopes with constant metric dimension, Computers and Mathematics with Applications, 60, 2629-2638 (2010) · Zbl 1205.05067 [23] Javaid, I.; Rahim, M.; Ali, K., Families of regular graphs with constant metric dimension, Utilitas Mathematica, 75, 21-33 (2008) · Zbl 1178.05037 [24] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Applied Mathematics, 70, 217-229 (1996) · Zbl 0865.68090 [25] Kochetov, Y.; Kononova, P.; Paschenko, M., Formulation space search approach for the teacher/class timetabling problem, Yugoslav Journal of Operations Research, 18, 1-11 (2008) · Zbl 1235.90064 [26] Kratica, J.; Kovačević-Vujčić, V.; Čangalović, M., Computing strong metric dimension of some special classes of graphs by genetic algorithms, Yugoslav Journal of Operations Research, 18, 143-151 (2008) · Zbl 1199.68546 [27] Kratica, J.; Kovačević-Vujčić, V.; Čangalović, M., Computing the metric dimension of graphs by genetic algorithms, Computational Optimization and Applications, 44, 343-361 (2009) · Zbl 1191.68469 [28] Kratica, J.; Čangalović, M.; Kovačević-Vujčić, V., Computing minimal doubly resolving sets of graphs, Computers & Operations Research, 36, 2149-2159 (2009) · Zbl 1158.90414 [29] Mansini, R., Labadie, N., Melechovský, J., & Calvo, R., in press. The team orienteering problem with time windows: an LP-based granular variable neighborhood search. European Journal of Operational Research. doi:10.1016/j.ejor.2012.01.030; Mansini, R., Labadie, N., Melechovský, J., & Calvo, R., in press. The team orienteering problem with time windows: an LP-based granular variable neighborhood search. European Journal of Operational Research. doi:10.1016/j.ejor.2012.01.030 · Zbl 1253.90048 [30] Manuel, P.; Rajasingh, I., Minimum metric dimension of silicate networks, Ars Combinatoria, 98, 501-510 (2011) · Zbl 1249.05359 [31] Mladenović, N.; Hansen, P., Variable neighbourhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 [32] Mladenović, N.; Plastria, F.; Urošević, D., Reformulation descent applied to circle packing problems, Computers & Operations Research, 32, 2419-2434 (2005) · Zbl 1066.90092 [33] Mladenović, N.; Plastria, F.; Urosević, D., Formulation space search for circle packing problems, Lecture Notes in Computer Science, 4638, 212-216 (2007) · Zbl 1134.90477 [34] Mladenović, N.; Urošević, D.; Pérez-Brito, D.; Garcfa-González, C., Variable neighbourhood search for bandwidth reduction, European Journal of Operational Research, 200, 14-27 (2010) · Zbl 1188.90217 [35] Mladenović, N., Urošević, D., Hanafi, S., & Ilić, A., in press. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research. doi:10.1016/j.ejor.2012.01.036; Mladenović, N., Urošević, D., Hanafi, S., & Ilić, A., in press. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research. doi:10.1016/j.ejor.2012.01.036 · Zbl 1253.90200 [36] Muller, L.; Spoorendonk, S.; Pisinger, D., A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times, European Journal of Operational Research, 218, 614-623 (2012) · Zbl 1244.90170 [37] Peters-Fransen, J.; Oellermann, O., The metric dimension of cartesian products of graphs, Utilitas Mathematica, 69, 33-41 (2006) · Zbl 1109.05041 [38] Rebatel, F.; Thiel, E., Metric bases for polyhedral gauges, Lecture Notes in Computer Science, 6607, 116-128 (2011) · Zbl 1272.52025 [39] Sebo, A.; Tannier, E., On metric generators of graphs, Mathematics & Operations Research, 29, 383-393 (2004) · Zbl 1082.05032 [40] Slater, P., Leaves of trees, Congressus Numerantium, 14, 549-559 (1975) [41] Sudhakara, G.; Kumar, A. H., Graphs with metric dimension two – a characterization, World Academy of Science, Engineering and Technology, 60, 621-626 (2009) [42] Xiao, Y.; Kaku, I.; Zhao, Q.; Zhang, R., A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems, European Journal of Operational Research, 214, 223-231 (2012) · Zbl 1218.90076 [43] Yero, I.; Kuziak, D.; Rodriguez-Velazquez, J., On the metric dimension of corona product graphs, Computers and Mathematics with Applications, 61, 2793-2798 (2011) · Zbl 1221.05252 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.