×

A general variable neighborhood search for the cyclic antibandwidth problem. (English) Zbl 1487.90617

Summary: Graph Layout Problems refer to a family of optimization problems where the aim is to assign the vertices of an input graph to the vertices of a structured host graph, optimizing a certain objective function. In this paper, we tackle one of these problems, named Cyclic Antibandwidth Problem, where the objective is to maximize the minimum distance of all adjacent vertices, computed in a cycle host graph. Specifically, we propose a General Variable Neighborhood Search which combines an efficient Variable Neighborhood Descent with a novel destruction-reconstruction shaking procedure. Additionally, our proposal takes advantage of two new exploration strategies for this problem: a criterion for breaking the tie of solutions with the same objective function and an efficient evaluation of neighboring solutions. Furthermore, two new neighborhood reduction strategies are proposed. We conduct a thorough computational experience by comparing the algorithm proposed with the current state-of-the-art methods over a set of previously reported instances. The associated results show the merit of the introduced algorithm, emerging as the best performance method in those instances where the optima are unknown. These results are further confirmed with nonparametric statistical tests.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, RK; Ergun, O.; Orlin, JB; Punnen, AP, A survey of very large-scale neighborhood search techniques, Discret. Appl. Math., 123, 1, 75-102 (2002) · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[2] Alway, G.; Martin, D., An algorithm for reducing the bandwidth of a matrix of symmetrical configuration, Comput. J., 8, 3, 264-272 (1965) · Zbl 0147.13103 · doi:10.1093/comjnl/8.3.264
[3] Bansal, R.; Srivastava, K., A memetic algorithm for the cyclic antibandwidth maximization problem, Soft. Comput., 15, 2, 397-412 (2011) · doi:10.1007/s00500-009-0538-6
[4] Bhatt, SN; Thomson Leighton, F., A framework for solving VLSI graph layout problems, J. Comput. Syst. Sci., 28, 2, 300-343 (1984) · Zbl 0543.68052 · doi:10.1016/0022-0000(84)90071-0
[5] Cavero, S.; Pardo, EG; Laguna, M.; Duarte, A., Multistart search for the cyclic cutwidth minimization problem, Comput. Oper. Res., 126, 105-116 (2021) · Zbl 1510.90218 · doi:10.1016/j.cor.2020.105116
[6] Dobrev, S., Královič, R., Pardubská, D., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of Hamming graphs. Discret. Appl. Math. 161(10), 1402-1408 (2013) · Zbl 1287.05133
[7] Duarte, A.; Escudero, LF; Martí, R.; Mladenovic, N.; Pantrigo, JJ; Sánchez-Oro, J., Variable neighborhood search for the vertex separation problem, Comput. Oper. Res., 39, 12, 3247-3255 (2012) · Zbl 1349.90809 · doi:10.1016/j.cor.2012.04.017
[8] Duarte, A.; Pantrigo, JJ; Pardo, EG; Sánchez-Oro, J., Parallel variable neighbourhood search strategies for the cutwidth minimization problem, IMA J. Manag. Math., 27, 1, 55-73 (2016) · Zbl 1433.90132 · doi:10.1093/imaman/dpt026
[9] Duarte, A.; Sánchez-Oro, J.; Mladenović, N.; Todosijević, R.; Martí, R.; Pardalos, PM; Resende, MGC, Variable Neighborhood Descent, Handbook of Heuristics, 341-367 (2018), Cham: Springer, Cham · doi:10.1007/978-3-319-07124-4_9
[10] Duff, IS; Grimes, RG; Lewis, JG, Users Guide for the Harwell-Boeing Sparse Matrix Collection (Release I) (1992), Chilton: RAL, Chilton
[11] Díaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Comput. Surv., 34, 3, 313-356 (2002) · doi:10.1145/568522.568523
[12] Hale, W., Frequency assignment: theory and applications, Proc. IEEE, 68, 12, 1497-1514 (1980) · doi:10.1109/PROC.1980.11899
[13] Hansen, P.; Mladenović, N.; Burke, EK; Kendall, G., Variable Neighborhood Search, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, 313-337 (2014), US, Boston, MA: Springer, US, Boston, MA · doi:10.1007/978-1-4614-6940-7_12
[14] Hansen, P.; Mladenović, N.; Todosijević, R.; Hanafi, S., Variable neighborhood search: basics and variants, EURO J. Comput. Optim., 5, 3, 423-454 (2017) · Zbl 1390.90586 · doi:10.1007/s13675-016-0075-x
[15] Harper, LH, Optimal numberings and isoperimetric problems on graphs, J. Comb. Theory, 1, 3, 385-393 (1966) · Zbl 0158.20802 · doi:10.1016/S0021-9800(66)80059-5
[16] Hromkovic, J.; Muller, V.; Sykora, O.; Vrto, I., On embeddings in cycles, Inf. Comput., 118, 2, 302-305 (1995) · Zbl 0826.68012 · doi:10.1006/inco.1995.1068
[17] Jain, P.; Srivastava, K.; Saran, G., Minimizing cyclic cutwidth of graphs using a memetic algorithm, J. Heurist., 22, 6, 815-848 (2016) · doi:10.1007/s10732-016-9319-4
[18] Leung, JY-T; Vornberger, O.; Witthoff, JD, On some variants of the bandwidth minimization problem, SIAM J. Comput., 13, 3, 650-667 (1984) · Zbl 0545.68058 · doi:10.1137/0213040
[19] López-Ibá nez, M., Dubois-Lacoste, J., P. Cáceres, L., Birattari, M., Stützle, T.: Iterated racing for automatic algorithm configuration. The irace package. Oper. Res. Perspect. 3, 43-58 (2016)
[20] Lozano, M.; Duarte, A.; Gortázar, F.; Martí, R., A hybrid metaheuristic for the cyclic antibandwidth problem, Knowl. Based Syst., 54, 103-113 (2013) · doi:10.1016/j.knosys.2013.08.026
[21] Martí, R.: Multi-start methods. In: Handbook of Metaheuristics. International Series in Operations Research and Management Science, pp. 355-368. Springer, Boston (2003) · Zbl 1102.90383
[22] Martí, R.; Laguna, M.; Glover, F.; Campos, V., Reducing the bandwidth of a sparse matrix with tabu search, Eur. J. Oper. Res., 135, 2, 450-459 (2001) · Zbl 1051.90031 · doi:10.1016/S0377-2217(00)00325-8
[23] Martí, R.; Pantrigo, J-J; Duarte, A.; Campos, V.; Glover, F., Scatter search and path relinking : a tutorial on the linear arrangement problem, Int. J. Swarm Intell. Res. (IJSIR), 2, 2, 1-21 (2011) · doi:10.4018/jsir.2011040101
[24] Miller, Z.; Pritikin, D., On the separation number of a graph, Networks, 19, 6, 651-666 (1989) · Zbl 0677.90076 · doi:10.1002/net.3230190604
[25] Mladenović, N.; Dražić, M.; Kovačevic-Vujčić, V.; Čangalović, M., General variable neighborhood search for the continuous optimization, Eur. J. Oper. Res., 191, 3, 753-770 (2008) · Zbl 1156.90005 · doi:10.1016/j.ejor.2006.12.064
[26] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 11, 1097-1100 (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[27] Pardo, EG; Martí, R.; Duarte, A.; Martí, R.; Panos, P.; Resende, MG, Linear Layout Problems, Handbook of Heuristics, 1-25 (2016), Cham: Springer, Cham
[28] Pardo, EG; Mladenović, N.; Pantrigo, JJ; Duarte, A., Variable formulation search for the cutwidth minimization problem, Appl. Soft Comput., 13, 5, 2242-2252 (2013) · doi:10.1016/j.asoc.2013.01.016
[29] Pardo, EG; Soto, M.; Thraves, C., Embedding signed graphs in the line, J. Comb. Optim., 29, 2, 451-471 (2015) · Zbl 1316.90058 · doi:10.1007/s10878-013-9604-1
[30] Pastore, T.; Martínez-Gavara, A.; Napoletano, A.; Festa, P.; Martí, R., Tabu search for min-max edge crossing in graphs, Comput. Oper. Res., 114, 104830 (2020) · Zbl 1458.90621 · doi:10.1016/j.cor.2019.104830
[31] Piñana, E.; Plana, I.; Campos, V.; Martí, R., GRASP and path relinking for the matrix bandwidth minimization, Eur. J. Oper. Res., 153, 1, 200-210 (2004) · Zbl 1053.90057 · doi:10.1016/S0377-2217(02)00715-4
[32] Raspaud, A., Schröder, H., Sýkora, O., Torok, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discret. Math. 309(11), 3541-3552 (2009) · Zbl 1209.05216
[33] Raspaud, A., Sýkora, O., Vrt’o, I.: Congestion and dilation, similarities and differences: a survey. In: Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity, pp. 14 (2000)
[34] Ren, J.; Hao, J-K; Rodriguez-Tello, E.; Li, L.; He, K., A new iterated local search algorithm for the cyclic bandwidth problem, Knowl. Based Syst., 203, 106-136 (2020) · doi:10.1016/j.knosys.2020.106136
[35] Rodriguez-Tello, E.; Hao, J-K; Torres-Jimenez, J., An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem, Comput. Oper. Res., 35, 10, 3331-3346 (2008) · Zbl 1133.90424 · doi:10.1016/j.cor.2007.03.001
[36] Rodriguez-Tello, E.; Lardeux, F.; Duarte, A.; Narvaez-Teran, V., Alternative evaluation functions for the cyclic bandwidth sum problem, Eur. J. Oper. Res., 273, 3, 904-919 (2019) · Zbl 1403.90656 · doi:10.1016/j.ejor.2018.09.031
[37] Rodriguez-Tello, E.; Narvaez-Teran, V.; Lardeux, F., Dynamic multi-armed bandit algorithm for the cyclic bandwidth sum problem, IEEE Access, 7, 40258-40270 (2019) · doi:10.1109/ACCESS.2019.2906840
[38] Rodriguez-Tello, E.; Romero-Monsivais, H.; Ramirez-Torres, G.; Lardeux, F., Tabu search for the cyclic bandwidth problem, Comput. Oper. Res., 57, 17-32 (2015) · Zbl 1348.90604 · doi:10.1016/j.cor.2014.11.013
[39] Rost, M., Schmid, S.: Charting the complexity landscape of virtual network embeddings. In: 2018 IFIP Networking Conference (IFIP Networking) and Workshops, pp. 1-9 (2018)
[40] Skiena, SS, Graph Traversal (1997), Berlin: Springer Publishing Company, Berlin
[41] Sánchez-Oro, J.; José Pantrigo, J.; Duarte, A., Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Comput. Oper. Res., 52, 209-219 (2014) · Zbl 1348.90606 · doi:10.1016/j.cor.2013.11.008
[42] Sýkora, O., Torok, L., Vrt’o, I.: The cyclic antibandwidth problem. Electr. Notes Discrete Math. 22, 223-227 (2005) · Zbl 1200.05121
[43] Weili, Y.; Xiaoxu, L.; Ju, Z., Dual bandwidth of some special trees, Journal-Zhengzhou Univ. Nat. Sci. Ed., 35, 3, 16-19 (2003)
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.