×

A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs. (English) Zbl 1360.05170

Summary: The bandwidth minimization problem on graphs (BMPG) consists of labeling the vertices of a graph with the integers from 1 to \( n\) (\( n\) is the number of vertices) such that the maximum absolute difference between labels of adjacent vertices is as small as possible. In this work we develop a DRSA (Dual Representation Simulated Annealing) algorithm to solve BMPG. The main novelty of DRSA is an internal dual representation of the problem used in conjunction with a neighborhood function composed of three perturbation operators. The evaluation function of DRSA is able to discriminate among solutions of equal bandwidth by taking into account all absolute differences between labels of adjacent vertices. For better performance, the parameters of DRSA and the probabilities for selecting the perturbation operators were tuned by extensive experimentation carried out using a full factorial design. The benchmark for the proposed algorithm consists of 113 instances of the Harwell-Boeing sparse matrix collection; the results of DRSA included 31 new upper bounds and the matching of 82 best-known solutions (22 solutions are optimal). We used Wilcoxon signed-rank test to compare best solutions produced by DRSA against best solutions produced by three state of the art methods: greedy randomized adaptive search procedure with path relinking, simulated annealing, and variable neighborhood search; according to the comparisons done, the quality of the solutions with DRSA is significantly better than that obtained with the other three algorithms.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. H.L.; Korst, J. H.M.; van Laarhoven, P. J.M., Simulated annealing, (Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (2003), Princeton University Press: Princeton University Press Princeton, NJ, USA), 91-120 · Zbl 0905.90140
[2] Berry, M. W.; Hendrickson, B.; Raghavan, P., Sparse matrix reordering schemes for browsing hypertext, Lect. Appl. Math., 32, 99-123 (1996) · Zbl 0857.68036
[3] Bhatt, S. N.; Leighton, F. T., A framework for solving {VLSI} graph layout problems, J. Comp. Syst. Sci., 28, 2, 300-343 (1984) · Zbl 0543.68052
[4] Campos, V.; Piñana, E.; Martí, R., Adaptive memory programming for matrix bandwidth minimization, Ann. Operat. Res., 183, 1, 7-23 (2006) · Zbl 1213.90208
[5] Caprara, A.; Salazar-González, J. J., Laying out sparse graphs with provably minimum bandwidth, INFORMS J. Comput., 17, 3, 356-373 (2005) · Zbl 1239.90106
[6] Cuthill, E.; McKee, J., Reducing the bandwidth of sparse symmetric matrices, (Proceedings of the 1969 24th National Conference, ACM ’69 (1969), ACM: ACM New York, NY, USA)
[7] Cygan, M.; Pilipczuk, M., Faster exact bandwidth, (Lecture Notes in Artificial Intelligence, vol. 1952 (2000), Springer: Springer Berlin/Heidelberg), 477-486
[8] Cygan, M.; Pilipczuk, M., Faster exact bandwidth, (Broersma, H.; Erlebach, T.; Friedetzky, T.; Paulusma, D., Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 5344 (2008), Springer: Springer Berlin/Heidelberg), 101-109 · Zbl 1202.05135
[9] Cygan, M.; Pilipczuk, M., Even faster exact bandwidth, ACM Trans. Algor., 8, 1, 8:1-8:14 (2012) · Zbl 1295.68130
[10] Del Corso, G. M.; Manzini, G., Finding exact solutions to the bandwidth minimization problem, Computing, 62, 189-203 (1999) · Zbl 0946.65030
[11] Dueck, G. W.; Jeffs, J., A heuristic bandwidth reduction algorithm, J. Combinat. Math. Comp., 18, 97-108 (1995) · Zbl 0833.68094
[12] Esposito, A.; Catalano, M.; Malucelli, F.; Tarricone, L., Sparse matrix bandwidth reduction: algorithms, applications and real industrial cases in electromagnetics, (Arbenz, P.; Paprzycki, M.; Sameh, A.; Sarin, V., High Performance Algorithms for Structured Matrix Problems (1998), Nova Science Publisher, Inc.), 27-45 · Zbl 0968.78006
[15] Harary, F., Theory of Graphs and its Applications (1967), Czechoslovak Academy of Science: Czechoslovak Academy of Science Prague
[16] Harper, L. H., Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math., 12, 1, 131-135 (1964) · Zbl 0222.94004
[17] Koohestani, B.; Poli, R., A genetic programming approach to the matrix bandwidth-minimization problem, (Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part II, PPSN’10 (2010), Springer-Verlag: Springer-Verlag Berlin, Heidelberg)
[18] Lim, A.; Lin, J.; Rodrigues, B.; Xiao, F., Ant colony optimization with hill climbing for the bandwidth minimization problem, Appl. Soft Comput., 6, 2, 180-188 (2006)
[19] Lim, A.; Rodrigues, B.; Xiao, F., Heuristics for matrix bandwidth reduction, Euro. J. Operat. Res., 174, 1, 69-91 (2006) · Zbl 1116.90118
[20] Martí, R.; Campos, V.; Piñana, E., A branch and bound algorithm for the matrix bandwidth minimization, Euro. J. Operat. Res., 186, 2, 513-528 (2008) · Zbl 1138.90037
[21] Martí, R.; Laguna, M.; Glover, F.; Campos, V., Reducing the bandwidth of a sparse matrix with tabu search, Euro. J. Operat. Res., 135, 2, 450-459 (2001) · Zbl 1051.90031
[23] Mladenović, N.; Urošević, D.; Pérez-Brito, D.; García-González, C. G., Variable neighbourhood search for bandwidth reduction, Euro. J. Operat. Res., 200, 1, 14-27 (2010) · Zbl 1188.90217
[24] Monien, B.; Sudborough, I. H., Bandwidth constrained np-complete problems, (Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, STOC ’81 (1981), ACM: ACM New York, NY, USA)
[25] Papadimitriou, C., The np-completeness of the bandwidth minimization problem, J. Comput., 16, 263-270 (1976) · Zbl 0321.65019
[26] Piñana, E.; Plana, I.; Campos, V.; Martí, R., Grasp and path relinking for the matrix bandwidth minimization, Euro. J. Operat. Res., 153, 1, 200-210 (2004) · Zbl 1053.90057
[27] Rodriguez-Tello, E.; Hao, J. K.; Torres-Jimenez, J., An improved simulated annealing algorithm for bandwidth minimization, Euro. J. Operat. Res., 185, 3, 1319-1335 (2008) · Zbl 1146.90518
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.