Desigualdades válidas para o problema do caminho positivo mínimo em digrafos de sinais - Sombra, João Victor Fonseca; Andrade, Rafael Castro de; Campêlo Neto, Manoel Bezerra (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
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.