Matroides e interseção de matroides em problemas de otimização combinatória

Abstract

Nesta tese são revistos conceitos básicos que relacionam a teoria dos matroides com a otimização combinatória. São expostos, de forma uniformizada, vários resultados e conceitos bem conhecidos, mas apresentados em textos diversos. Além dos conceitos básicos são igualmente apresentados algoritmos exatos que permitem resolver problemas de otimização cujo conjunto de soluções admissíveis forma um matroide ou corresponde à interseção de dois matroides. É dado ênfase ao estudo poliédrico dos problemas de otimização. Em particular são estudadas algumas relações da função caraterística com restrições e desigualdades válidas para vários problemas de otimização bem conhecidos, como o problema do Saco-Mochila e da Arvore de Suporte de Custo Mínimo. Seguindo Amado, 1997, é estudada a estrutura poliédrica de famílias particulares do problema de sacomochila cuja descrição poliédrica é feita com base em desigualdades de cobertura estendida. Com base nessa família são apresentados minorantes e majorantes para o problema do saco-mochila.

In this thesis we revise basic concepts relating matroid theory with combinatorial otimization. We present, in an uni ed way, several well-known results and concepts that are given in di erent sources. In addition to the basic concepts we also give exact algorithms for otimization problems where the feasible set is either a matroid or it can be obtained as the intersection of two matroids. We focus on the polyhedral study of the otimization problem. In particular, we study the relation between the characteristic function and constraints and valid inequalities for several well-known optimization problems as the knapsack problem and the minimum spanning tree. Following Amado, 1997, we study the polyhedral of particular families of the knapsack problem whose polyhedral description is based on extended cover inequalities. Based on those families we discuss lower and upper bounds for the knapsack problem.