A GRASP Approach for The Minimum Spanning Tree Under Conflict Constraints
Abstract
Given an undirected graph with weights on the edges and a set of conflicting edge pairs, the Minimum Spanning Tree Under Conflict Constraints (MSTCC) consists in finding a minimum spanning tree with at most one edge of each conflicting pair and minimum cost. The problem is NP-hard and was introduces recently at literature. This paper proposes a new approach for solving MSTCC, our method is based on the GRASP metaheuristic coupled with adaptive memory programming. We test the proposed heuristic on literatures instances with thousands of conflicts. The results indicate that the proposed algorithm was able to find all known optimal solutions and outperform the best-known heuristics for the MSTCC.
Keywords:
Spanning Tree Problem, Conflict Constraints, GRASP, Combinatorial Optimization, Smart Algorithms
References
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.
Published
2019-10-15
How to Cite
BARROS, Bruno; PINHEIRO, Rian; OCHI, Luiz; RAMOS, Geymerson.
A GRASP Approach for The Minimum Spanning Tree Under Conflict Constraints. In: NATIONAL MEETING ON ARTIFICIAL AND COMPUTATIONAL INTELLIGENCE (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.
