O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

In this thesis we discuss several formulations and different methods to solve the Weight-constrained Minimum Spanning Tree Problem (WMST). This problem, with applications in the design of communication networks and telecommunications, is a NP-hard combinatorial optimization problem. The WMST problem aims at obtaining, in a network with costs and weights associated to its edges, a minimum cost spanning tree such that its total weight does not exceed a given specified parameter. Various formulations to the problem are presented and compared. One is used to develop a procedure to introduce cuts based on separation and that became quite useful in obtaining solutions to the problem. To strengthen the formulations, new classes of valid inequalities, adapted from the well-known cover inequalities, extended cover inequalities and lifted cover inequalities, are introduced. These new inequalities incorporate information from two sets of solutions: the spanning trees set and the knapsack set. We present several separation heuristic algorithms that allow us to efficiently use the proposed valid inequalities. Based on Lagrangean decomposition, simple and efficient algorithms are presented and compared. The algorithms can be used to obtain upper and lower bounds to the optimal value of the WMST problem. Among them are two new algorithms: one based on the convexity of the Lagrangean function and another making use of the inclusion of valid inequalities. In order to obtain approximate solutions to the WMST problem, heuristic methods are used to find feasible solutions. The heuristic methods presented are based on the Feasibility Pump and Local Branching strategies. We present computational results using all these methods. Results show that the different methods presented are very efficient for finding solutions to the WMST problem.

Doutoramento em Matemática