Desigualdades válidas para o problema do caminho positivo mínimo em digrafos de sinais
Resumo
Apresentamos novas desigualdades válidas para o problema do caminho positivo mais curto em digrafos de sinais. Essas desigualdades não somente fortalecem a relaxação linear do modelo matemático mais conhecido para o problema, mas também reduzem significativamente os tempos de execução na resolução ótima de instâncias geradas aleatoriamente. Em média, nossa abordagem proporciona uma redução de 98,1% no tempo de execução em comparação com o modelo existente na literatura.Referências
Albuquerque, F. (2023). Problema de formação de equipes com caminhos positivos. Master’s thesis, Universidade Federal do Ceará, Fortaleza, CE, Brasil.
Costa, I. S., Figueiredo, R., and Requejo, C. (2023). The shortest path in signed graphs. In Operational Research, pages 53–71, Cham. Springer International Publishing.
Desrochers, M. and Laporte, G. (1991). Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints. Operations Research Letters, 10(1):27–36.
Hansen, P. (1984). Shortest paths in signed graphs. In Burkard, R., Cuninghame-Green, R., and Zimmermann, U., editors, Algebraic and Combinatorial Methods in Operations Research, volume 95 of North-Holland Mathematics Studies, pages 201–214. North-Holland.
Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143 – 146.
Heider, F. (1946). Attitudes and cognitive organization. The Journal of Psychology, 21(1):107–112.
Kouvatis, I., Semertzidis, K., Zerva, M., Pitoura, E., and Tsaparas, P. (2020). Forming compatible teams in signed networks. CoRR, abs/2001.03128.
Lappas, T., Liu, K., and Terzi, E. (2009). Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, page 467–476, New York, NY, USA. Association for Computing Machinery.
Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329.
Costa, I. S., Figueiredo, R., and Requejo, C. (2023). The shortest path in signed graphs. In Operational Research, pages 53–71, Cham. Springer International Publishing.
Desrochers, M. and Laporte, G. (1991). Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints. Operations Research Letters, 10(1):27–36.
Hansen, P. (1984). Shortest paths in signed graphs. In Burkard, R., Cuninghame-Green, R., and Zimmermann, U., editors, Algebraic and Combinatorial Methods in Operations Research, volume 95 of North-Holland Mathematics Studies, pages 201–214. North-Holland.
Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143 – 146.
Heider, F. (1946). Attitudes and cognitive organization. The Journal of Psychology, 21(1):107–112.
Kouvatis, I., Semertzidis, K., Zerva, M., Pitoura, E., and Tsaparas, P. (2020). Forming compatible teams in signed networks. CoRR, abs/2001.03128.
Lappas, T., Liu, K., and Terzi, E. (2009). Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, page 467–476, New York, NY, USA. Association for Computing Machinery.
Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329.
Publicado
20/07/2025
Como Citar
SOMBRA, João Victor Fonseca; ANDRADE, Rafael Castro de; CAMPÊLO NETO, Manoel Bezerra.
Desigualdades válidas para o problema do caminho positivo mínimo em digrafos de sinais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 21-25.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.7617.
