Large neighbourhood search para o problema do safe set

• José Paulo de Faria Pedrosa UFMS
• Edna A. Hoshino UFMS
• Vagner Pedrotti UFMS

DOI: https://doi.org/10.5753/etc.2024.3098

Resumo

O problema do safe set consiste em encontrar um subconjunto de vértices de peso mínimo, que possui componentes conexas que dominam as componentes conexas adjacentes. Neste trabalho, propomos um método de duas fases para construir soluções para o problema do safe set. Uma solução inicial é obtida por uma fase construtiva e otimizada por procedimentos de large neighbourhood search. Experimentos computacionais em instâncias da literatura mostram que a matheurística melhora, em média, em 50% o valor da solução.

Referências

Bapat, R., Fujita, S., Legay, S., Manoussakis, Y., Matsui, Y., Sakuma, T., and Tuza, Z. (2016). Network majority on tree topological network. Electron. Notes Discrete Math., 54:79–84.

Fujita, S., MacGillivray, G., and Sakuma, T. (2016). Safe set problem on graphs. Discrete Applied Mathematics, 215:106–111.

Hosteins, P. (2020). A compact mixed integer linear formulation for safe set problems. Optimization Letters, 14:2127–2148.

Macambira, A. F. U., Simonetti, L., Barbalho, H., Gonzalez, P. H., and Maculan, N. (2019). A new formulation for the safe set problem on graphs. Computers and Operations Research, 111:346–356.

Malaguti, E. and Pedrotti, V. (2023). Models and algorithms for the weighted safe set problem. Discrete Applied Mathematics, 329:23–34.

Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In Maher, M. and Puget, J.-F., editors, Principles and Practice of Constraint Programming — CP98, pages 417–431, Berlin, Heidelberg. Springer.