A GRASP Approach for The Minimum Spanning Tree Under Conflict Constraints
Resumo
Dados um grafo não direcionado com pesos nas arestas e um conjunto de pares de arestas conflitantes, a Árvore de Geradora Mı́nima com Restrições de Conflito (AGMRC) consiste em encontrar árvore geradora com no máximo uma aresta de cada par conflitante e custo mı́nimo. O problema é N P-difı́cil e foi introduzido recentemente na literatura. Este artigo propõe uma nova abordagem para a solução do AGMRC, o método é baseado na meta-heurı́stica GRASP com uso de uma memória adaptativa. A heurı́stica proposta foi avaliada nas instâncias da literatura com milhares de conflitos. Os resultados indicam que o algoritmo proposto foi capaz de encontrar todas as soluções ótimas conhecidas e superar as heurı́sticas da literatura para o AGMRC.
Palavras-chave:
Árvore Geradora Mı́nima, Restrições de Conflitos, GRASP, Otimização Combinatória, Algoritmos Inteligentes
Referências
Aiex, R. M., Resende, M. G. C., and Ribeiro, C. C. (2007). Ttt plots: a perl program to create time-to-target plots. Optimization Letters, 1(4):355–366.
Barbosa, M. A. L. and Delbem, A. C. B. (2017). Uma busca local iterada para o problema da árvore geradora mı́nima sob restrições de conflitos. Anais do XLVIII Simpósisileiro de Pesquisa Operacional.
Binato, S., J. Hery, W., and M. Loewenstern, D. (2000). A grasp for job shop scheduling. Essays and Surveys on Metaheuristics, 15.
Bittencourt, Y. B., , Campêlo, M., and Dias, F. C. S. (2016). Formulaçao mtz para o pblema da Árvore geradora mınima sob restriçoes de conflito. Anais do XLVIII Simpósio de Pesquisa Operacional.
Bresina, J. L. (1996). Heuristic-biased stochastic sampling. In AAAI/IAAI, Vol. 1, pages 271–278.
Capua, R., Frota, Y., Vidal, T., and Ochi, L. S. (2015). Um algoritmo heurıstico para o problema de bin packing com conflitos. Anais do XLVII Simpósio Brasileiro de Pesquisa Operacional.
Carrabs, F., Cerrone, C., and Pentangelo, R. (2017). A multiethnic genetic approach for the minimum conflict weighted spanning tree problem. Networks.
Carrabs, F., Cerulli, R., Pentangelo, R., and Raiconi, A. (2018). Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach. Annals of Operations Research, pages 1–14.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2002). Algoritmos: Teoria e Prática. Elsevier, 2 edition. ISBN 85-352-0926-3.
Darmann, A., Pferschy, U., and Schauer, J. (2009). Determining a minimum spanning tree with disjunctive constraints. In International Conference on Algorithmic DecisionTheory, pages 414–423. Springer.
Darmann, A., Pferschy, U., Schauer, J., and Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159(16):1726– 1735.
Expósito, A., Brito, J., and Moreno, J. A. (2016). A heuristic-biased grasp for the team orienteering problem. In Conference of the Spanish Association for Artificial Intelligence, pages 428–437. Springer.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Gonçalves, L. B., Ochi, L. S., and Martins, S. L. (2005). A grasp with adaptive memory for a period vehicle routing problem. In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), volume 1, pages 721–727. IEEE.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48–50.
Motta, L. C. and Ochi, L. S. (2009). Metaheurı́sticas com memória adaptativa para o problema de recobrimento de rotas. In IX Congresso Brasileiro de Redes Neurais.
Neves, T. A. and Ochi, L. S. (2009). Grasp com memória adaptativa na solução de um blema de roteamento de veı́culos com múltiplas origens. Anais do XXXVIII Simpósio Brasileiro de Pesquisa Operacional.
Resende, M. G. and Ribeiro, C. C. (2016). Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer-Verlag New York, 1 edition.
Samer, P. and Urrutia, S. (2013). Um algoritmo de branch and cut para árvores geradoras mınimas sob restriçoes de conflito. Anais do XLV Simpósio Brasileiro de Pesquisa Operacional.
Samer, P. and Urrutia, S. (2015). A branch and cut algorithm for minimum spanning trees under conflict constraints. Optimization Letters, 9(1):41–55.
Zhang, R., Kabadi, S. N., and Punnen, A. P. (2011). The minimum spanning tree problem with conflict constraints and its variations. Discrete Optimization, 8(2):191–205.
Barbosa, M. A. L. and Delbem, A. C. B. (2017). Uma busca local iterada para o problema da árvore geradora mı́nima sob restrições de conflitos. Anais do XLVIII Simpósisileiro de Pesquisa Operacional.
Binato, S., J. Hery, W., and M. Loewenstern, D. (2000). A grasp for job shop scheduling. Essays and Surveys on Metaheuristics, 15.
Bittencourt, Y. B., , Campêlo, M., and Dias, F. C. S. (2016). Formulaçao mtz para o pblema da Árvore geradora mınima sob restriçoes de conflito. Anais do XLVIII Simpósio de Pesquisa Operacional.
Bresina, J. L. (1996). Heuristic-biased stochastic sampling. In AAAI/IAAI, Vol. 1, pages 271–278.
Capua, R., Frota, Y., Vidal, T., and Ochi, L. S. (2015). Um algoritmo heurıstico para o problema de bin packing com conflitos. Anais do XLVII Simpósio Brasileiro de Pesquisa Operacional.
Carrabs, F., Cerrone, C., and Pentangelo, R. (2017). A multiethnic genetic approach for the minimum conflict weighted spanning tree problem. Networks.
Carrabs, F., Cerulli, R., Pentangelo, R., and Raiconi, A. (2018). Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach. Annals of Operations Research, pages 1–14.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2002). Algoritmos: Teoria e Prática. Elsevier, 2 edition. ISBN 85-352-0926-3.
Darmann, A., Pferschy, U., and Schauer, J. (2009). Determining a minimum spanning tree with disjunctive constraints. In International Conference on Algorithmic DecisionTheory, pages 414–423. Springer.
Darmann, A., Pferschy, U., Schauer, J., and Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159(16):1726– 1735.
Expósito, A., Brito, J., and Moreno, J. A. (2016). A heuristic-biased grasp for the team orienteering problem. In Conference of the Spanish Association for Artificial Intelligence, pages 428–437. Springer.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Gonçalves, L. B., Ochi, L. S., and Martins, S. L. (2005). A grasp with adaptive memory for a period vehicle routing problem. In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), volume 1, pages 721–727. IEEE.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48–50.
Motta, L. C. and Ochi, L. S. (2009). Metaheurı́sticas com memória adaptativa para o problema de recobrimento de rotas. In IX Congresso Brasileiro de Redes Neurais.
Neves, T. A. and Ochi, L. S. (2009). Grasp com memória adaptativa na solução de um blema de roteamento de veı́culos com múltiplas origens. Anais do XXXVIII Simpósio Brasileiro de Pesquisa Operacional.
Resende, M. G. and Ribeiro, C. C. (2016). Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer-Verlag New York, 1 edition.
Samer, P. and Urrutia, S. (2013). Um algoritmo de branch and cut para árvores geradoras mınimas sob restriçoes de conflito. Anais do XLV Simpósio Brasileiro de Pesquisa Operacional.
Samer, P. and Urrutia, S. (2015). A branch and cut algorithm for minimum spanning trees under conflict constraints. Optimization Letters, 9(1):41–55.
Zhang, R., Kabadi, S. N., and Punnen, A. P. (2011). The minimum spanning tree problem with conflict constraints and its variations. Discrete Optimization, 8(2):191–205.
Publicado
15/10/2019
Como Citar
BARROS, Bruno; PINHEIRO, Rian; OCHI, Luiz; RAMOS, Geymerson.
A GRASP Approach for The Minimum Spanning Tree Under Conflict Constraints. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 166-177.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9281.
