×

A variable neighborhood search and simulated annealing hybrid for the profile minimization problem. (English) Zbl 1391.90529

Summary: Given an undirected simple graph \(G\), the profile minimization problem (PMP) is to find an ordering of the vertices of the graph \(G\) such that the sum of the profiles of all its vertices is minimized. The profile of the vertex \(v\) in position \(i\) is defined as \(\max \{0, i - h_v \}\), where \(h_{v}\) is the position of the leftmost vertex among all vertices adjacent to \(v\) in \(G\). We propose an approach for the PMP, which combines a variable neighborhood search (VNS) scheme with the multi-start simulated annealing (MSA) technique. The solution delivered by MSA is submitted as input to the VNS component of the method. The VNS algorithm heavily relies on a fast insertion neighborhood exploration procedure. We show that the time complexity of this procedure is \(O(n^2)\), where \(n\) is the order of \(G\). We have found empirically that it is advantageous to give between 50 and 75% of the computation time to MSA and the rest to VNS. The results of the computational experiments demonstrate the superiority of our MSA-VNS algorithm over the current state-of-the-art metaheuristic approaches for the PMP. Using MSA-VNS, we improved the best known solutions for 50 well-recognized benchmark PMP instances in the literature. The source code implementing MSA-VNS is made publicly available as a benchmark for future comparisons.

MSC:

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

References:

[1] Armstrong, B. A., Near-minimal matrix profiles and wavefronts for testing nodal resequencing algorithms., Int J Numer Methods Eng, 21, 10, 1785-1790, (1985) · Zbl 0578.65034
[2] Barnard, S.; Pothen, A.; Simon, H., A spectral algorithm for envelope reduction of sparse matrices., Numer Linear Algebra Appl, 2, 4, 317-334, (1995) · Zbl 0833.65038
[3] Bernardes J. . A, B.; de Oliveira SL, G., A systematic review of heuristics for profile reduction of symmetric matrices., Procedia Comput Sci, 51, 221-230, (2015)
[4] Berry M., W.; Hendrickson, B.; Raghavan, P., Sparse matrix reordering schemes for browsing hypertext., Renegar J, Shub M, Smale S, editors. Lectures in Applied Mathematics. Vol 32: The Mathematics of Numerical Analysis., 99-123, (1996), American Mathematical Society Press Park City, Utah, USA · Zbl 0857.68036
[5] Bolanos M., E.; Aviyente, S.; Radha, H., Graph entropy rate minimization and the compressibility of undirected binary graphs., Proceedings of IEEE Statistical Signal Processing Workshop (SSP), 109-112, (2012), Ann Arbor MI, USA
[6] Campos, V.; Piñana, E.; Martí, R., Adaptive memory programming for matrix bandwidth minimization., Ann Oper Res, 183, 7-23, (2011) · Zbl 1213.90208
[7] Černý, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm., J Optim Theory Appl, 45, 1, 41-51, (1985) · Zbl 0534.90091
[8] Cuthill, E.; McKee, J., Reducing the bandwidth of sparse symmetric matrices., Proceedings of the ACM 24th National Conference, 157-172, (1969)
[9] Davis, T. A.; Hu, Y., The university of florida sparse matrix collection., ACM Trans Math Softw, 38, 1, 1-25, (2011) · Zbl 1365.65123
[10] Davis, T. A.; Rajamanickam, S.; Sid-Lakhdar, W. M., A survey of direct methods for sparse linear systems., Acta Numer, 25, 383-566, (2016) · Zbl 1346.65011
[11] Duff, I. S.; Reid, J. K.; Scott, J. A., The use of profile reduction algorithms with a frontal code., Int J Numer Methods Eng, 28, 11, 2555-2568, (1989) · Zbl 0725.65045
[12] George, J. A., Computer implementation of the finite element method, (1971), Computer Science Department, Stanford University, Stanford, CA, USA, ph.d. thesis
[13] Gibbs, N. E., Algorithm 509: A hybrid profile reduction algorithm., ACM Trans Math Softw, 2, 4, 378-387, (1976)
[14] Gibbs, N. E.; Poole, W. G.; Stockmeyer, P. K., An algorithm for reducing the bandwidth and profile of a sparse matrix., SIAM J Numer Anal, 13, 2, 236-250, (1976) · Zbl 0329.65024
[15] Guan, Y.; Williams, K. L., Profile minimization on triangulated triangles., Discrete Math, 260, 1-3, 69-76, (2003) · Zbl 1019.05053
[16] Hager, W. W., Minimizing the profile of a symmetric matrix., SIAM J Sci Comput, 23, 5, 1799-1816, (2002) · Zbl 1014.65020
[17] Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications., Eur J Oper Res, 130, 3, 449-467, (2001) · Zbl 0981.90063
[18] Hansen, P.; Mladenović, N.; Moreno Pérez, J. A., Variable neighbourhood search: methods and applications., Ann Oper Res, 175, 367-407, (2010) · Zbl 1185.90211
[19] Higham, D. J., Unravelling small world networks., J Comput Appl Math, 158, 1, 61-74, (2003) · Zbl 1028.65034
[20] Hu, Y. F.; Scott, J. A., A multilevel algorithm for wavefront reduction., SIAM J Sci Comput, 23, 4, 1352-1375, (2001) · Zbl 0999.65022
[21] Isazadeh, A.; Izadkhah, H.; Mokarram, A. H., A learning based evolutionary approach for minimization of matrix bandwidth problem., Appl Math Inform Sci, 6, 1, 51-57, (2012)
[22] Kaveh, A.; Sharafi, P., Ordering for bandwidth and profile minimization problems via charged system search algorithm., IJST-T Civ Eng, 36, C1, 39-52, (2012)
[23] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162
[24] Koohestani, B.; Poli, R., Evolving an improved algorithm for envelope reduction using a hyper-heuristic approach., IEEE Trans Evol Comput, 18, 4, 543-558, (2014)
[25] Koohestani, B.; Poli, R., Addressing the envelope reduction of sparse matrices using a genetic programming system., Comput Optim Appl, 60, 3, 789-814, (2015) · Zbl 1326.90072
[26] Kumfert, G.; Pothen, A., Two improved algorithms for envelope and wavefront reduction., BIT, 37, 3, 559-590, (1997) · Zbl 0891.65043
[27] Kuo, D.; Chang, G. J., The profile minimization problem in trees., SIAM J Comput, 23, 1, 71-81, (1994) · Zbl 0794.05117
[28] Lewis, R. R., Simulated annealing for profile and fill reduction of sparse matrices., Int J Numer Methods Eng, 37, 6, 905-925, (1994) · Zbl 0807.65044
[29] Lin, Y.; Yuan, J., Profile minimization problem for matrices and graphs., Acta Math Appl Sin-E, 10, 1, 107-112, (1994) · Zbl 0804.05060
[30] Mafteiu-Scai LO, The bandwidths of a matrix. a survey of algorithms., An Univ Vest Timis Ser Mat-Inform, 52, 2, 183-223, (2014) · Zbl 1374.65082
[31] Matrix Market, 2011. http://math.nist.gov/MatrixMarket/collections/hb.html [accessed 19.12.16].
[32] Meijer, J., de Pol, J., 2015. Bandwidth and wavefront reduction for static variable ordering in symbolic model checking.ArXiv preprint. arXiv:1511.08678v1 [cs.SE].
[33] Mladenovic, N.; Urosevic, D.; Pérez-Brito, D.; García-González, C. G., Variable neighborhood search for bandwidth reduction., Eur J Oper Res, 200, 1, 14-27, (2010) · Zbl 1188.90217
[34] Mueller, C.; Martin, B.; Lumsdaine, A., A comparison of vertex ordering algorithms for large graph visualization., Proceedings of the 6th International Asia-Pacific Symposium on Visualization (APVIS’07), 141-148, (2007), Sydney Australia
[35] Palubeckis, G., Fast local search for single row facility layout., Eur J Oper Res, 246, 3, 800-814, (2015) · Zbl 1346.90515
[36] Palubeckis, G., 2016. The profile minimization problem. http://www.personalas.ktu.lt/ ginpalu/pmp.html[accessed 10.01.17]. · Zbl 1391.90529
[37] Palubeckis, G., Single row facility layout using multi-start simulated annealing., Comput Ind Eng, 103, 1-16, (2017)
[38] Paulino, G. H.; Menezes, I. F.M.; Gattass, M.; Mukherjee, S., Node and element resequencing using the Laplacian of a finite element graph: part I- general concepts and algorithm., Int J Numer Methods Eng, 37, 9, 1511-1530, (1994) · Zbl 0805.73065
[39] Paulino, G. H.; Menezes, I. F.M.; Gattass, M.; Mukherjee, S., Node and element resequencing using the Laplacian of a finite element graph: part II - implementation and numerical results., Int J Numer Methods Eng, 37, 9, 1531-1555, (1994) · Zbl 0805.73065
[40] Pop, P.; Matei, O.; Comes, C. A., Reducing the bandwidth of a sparse matrix with a genetic algorithm., Optimization, 63, 12, 1851-1876, (2014) · Zbl 1305.65136
[41] Reid, J. K.; Scott, J. A., Ordering symmetric sparse matrices for small profile and wavefront., Int J Numer Methods Eng, 45, 12, 1737-1755, (1999) · Zbl 0959.65059
[42] Reid, J. K.; Scott, J. A., Implementing hager’s exchange methods for matrix profile reduction., ACM Trans Math Softw, 28, 4, 377-391, (2002) · Zbl 1074.65046
[43] Rutenbar, R. A., Simulated annealing algorithms: an overview., IEEE Circuits Devices Mag, 5, 1, 19-26, (1989)
[44] Sánchez-Oro, J.; Laguna, M.; Duarte, A.; Martí, R., Scatter search for the profile minimization problem., Networks, 65, 1, 10-21, (2015)
[45] Sloan, S. W., An algorithm for profile and wavefront reduction of sparse matrices., Int J Numer Methods Eng, 23, 2, 239-251, (1986) · Zbl 0601.65027
[46] Tewarson, R. P., Sparse matrices., (1973), Academic Press; New York · Zbl 0262.65021
[47] Torres-Jimenez, J.; Izquierdo-Marquez, I.; Garcia-Robledo, A.; Gonzalez-Gomez, A.; Bernal, J.; Kacker, R. N., A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs., Inf Sci, 303, 33-49, (2015) · Zbl 1360.05170
[48] Xu, S.; Xue, W.; Lin, H. X., Performance modeling and optimization of sparse matrix-vector multiplication on NVIDIA CUDA platform., J Supercomput, 63, 3, 710-721, (2013)
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.