The Minimum Delay Upgrading Minimum Spanning Tree Problem

Em várias operações práticas, há um esforço contínuo para aprimorar sistemas e melhorar a eficiência. Para redes existentes, realizar melhorias geralmente é mais econômico do que construir novos componentes ou reconstruir a rede por completo. The Minimum Delay Upgrading Minimum Spanning Tree Problem (MDUMSTP) concentra-se na alocação de recursos limitados para atualizar uma rede existente e minimizar o atraso total da árvore geradora mínima após essas atualizações. Este problema é um caso específico de atualizações baseadas em nós, em que a atualização de um nó gera um custo, mas reduz os pesos de todas as arestas conectadas a ele. Neste trabalho, para resolver o MDUMSTP, propomos uma nova formulação baseada em Programação linear Inteira (IP) e a comparamos com o modelo exato encontrado na literatura. Ao incorporar a separação e adição de desigualdades válidas, aprimoramos a formulação, alcançando limites mais rígidos e melhor desempenho computacional. Além disso, introduzimos um procedimento de pré-processamento que reduz significativamente o tamanho das instâncias. Experimentos numéricos mostram que nosso algoritmo Branch-and-Cut supera o método exato existente na literatura em diversas instâncias de teste, e ainda, resolve até a otimalidade instâncias previamente não resolvidas.