A constructive parallel heuristic approach for the MWPSP
Resumo
Algorithms for the problem of identifying a maximum edge-weight planar subgraph of a given edge-weighted graph G are relevant in a wide variety of application areas. In this paper, we propose a new local search constructive heuristic for this NP-hard problem, along with a GPU-based algorithm designed to accelerate its computational process. The experimental findings demonstrated that considerable speedup is attainable while maintaining good-quality results.
Referências
Ahmadi-Javid, A., Ardestani-Jaafari, A., Foulds, L. R., Hojabri, H., and Farahani, R. Z. (2015). An algorithm and upper bounds for the weighted maximal planar graph problem. Journal of the Operational Research Society, 66(8):1399–1412.
Alexander, J. W. (1930). The combinatorial theory of complexes. Annals of Mathematics, 31(2):292–320.
Coelho, V. S., Martins, W. S., Foulds, L. R., Dias, E. S., Castonguay, D., and Longo, H. J. (2016). Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo. In XVII Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD 2016), pages 16–27.
Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge, UK.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. International Journal of Production Research, 16(1):27–37.
Giffin, J. W. (1984). Graph theoretic techniques for facilities layout. PhD thesis, University of Canterbury, Christchurch, New Zealand.
Jünger, M. and Mutzel, P. (1993). Solving the Maximum Planar Subgraph Problem by Branch and Cut. In Rinaldi G., W. L., editor, Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization (IPCO 3), pages 479–492.
Kirk, D. B. and Wen-Mei, W. H. (2016). Programming massively parallel processors: a hands-on approach. Morgan Kaufmann, San Francisco.
Lengauer, T. (2012). Combinatorial algorithms for integrated circuit layout. Springer Science & Business Media.
Massara, G. P., Di Matteo, T., and Aste, T. (2017). Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks, 5(2):1–18.
Migdalas, A., Pardalos, P., and Storøy, S. (2013). Parallel Computing in Optimization. Applied Optimization. Springer Science & Business Media, Heidelburg.
Pesch, E. (1999). Efficient facility layout planning in a maximally planar graph model. International Journal of Production Research, 37(2):263–283.
Seppänen, J. and Moore, J. M. (1970). Facilities Planning with Graph Theory. Management Science, 17(4):B–242–B–253.
Song, W.-M., Aste, T., and Di Matteo, T. (2007). Correlation-based biological networks. In Proceedings of International Symposium on Microelectronics, MEMS and Nanotechnology, volume 6802, pages 680212–1–680212–11, Canberra, Australia.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for filtering information in complex systems. Proceedings of the National Academy of Sciences of the United States of America, 102(30):10421–10426.
Alexander, J. W. (1930). The combinatorial theory of complexes. Annals of Mathematics, 31(2):292–320.
Coelho, V. S., Martins, W. S., Foulds, L. R., Dias, E. S., Castonguay, D., and Longo, H. J. (2016). Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo. In XVII Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD 2016), pages 16–27.
Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge, UK.
Foulds, L. R. and Robinson, D. F. (1978). Graph theoretic heuristics for the plant layout problem. International Journal of Production Research, 16(1):27–37.
Giffin, J. W. (1984). Graph theoretic techniques for facilities layout. PhD thesis, University of Canterbury, Christchurch, New Zealand.
Jünger, M. and Mutzel, P. (1993). Solving the Maximum Planar Subgraph Problem by Branch and Cut. In Rinaldi G., W. L., editor, Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization (IPCO 3), pages 479–492.
Kirk, D. B. and Wen-Mei, W. H. (2016). Programming massively parallel processors: a hands-on approach. Morgan Kaufmann, San Francisco.
Lengauer, T. (2012). Combinatorial algorithms for integrated circuit layout. Springer Science & Business Media.
Massara, G. P., Di Matteo, T., and Aste, T. (2017). Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks, 5(2):1–18.
Migdalas, A., Pardalos, P., and Storøy, S. (2013). Parallel Computing in Optimization. Applied Optimization. Springer Science & Business Media, Heidelburg.
Pesch, E. (1999). Efficient facility layout planning in a maximally planar graph model. International Journal of Production Research, 37(2):263–283.
Seppänen, J. and Moore, J. M. (1970). Facilities Planning with Graph Theory. Management Science, 17(4):B–242–B–253.
Song, W.-M., Aste, T., and Di Matteo, T. (2007). Correlation-based biological networks. In Proceedings of International Symposium on Microelectronics, MEMS and Nanotechnology, volume 6802, pages 680212–1–680212–11, Canberra, Australia.
Tumminello, M., Aste, T., Di Matteo, T., and Mantegna, R. N. (2005). A tool for filtering information in complex systems. Proceedings of the National Academy of Sciences of the United States of America, 102(30):10421–10426.
Publicado
17/10/2023
Como Citar
SILVA, Rafael C.; COELHO, Vinicius; MARTINS, Wellington; LONGO, Humberto; FOULDS, Leslie.
A constructive parallel heuristic approach for the MWPSP. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 24. , 2023, Porto Alegre/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 289-300.
DOI: https://doi.org/10.5753/wscad.2023.235873.
