Mochilas Matroidais

Abstract

Seja T a família de independentes de um matroide com conjunto de suporte Aí = {1,..., n} e seja B o conjunto dos vectores de incidência das bases do matroide. O problema da mochila matroidal consiste em calcular z = max{cx : x € V), onde V = {x € {0, l}n : ax < b, x € B), a = (ai,..., an) é um vector de inteiros não negativos e 6 > 0 é um inteiro. O problema da árvore de suporte com uma restrição adicional e o da mochila de escolha múltipla, que como é sabido são problemas «AA'P-completos, são casos particulares do problema da mochila matroidaL No entanto, há algumas instâncias que são fáceis de resolver: por exemplo, se {x € {0, l}n : ax < 6} for um matroide em Aí. Se não for este o caso, mostra-se como se pode calcular polinomialmente um majorante de z. Começa-se por cons¬truir uma desigualdade válida para V que seja uma relaxação matroidal do problema de mochila, com o objectivo de reforçar um dual lagrangeano do problema. Usando a descrição poliédrica das mochilas matroidais, prova-se que o majorante assim construído domina estritamente o da relaxação linear e pode ser obtido polinomialmente. Apresenta-se também uma heurística polinomial para o problema e o trabalho termina com a apresentação dos resultados da experiência com¬putacional com o objectivo de ilustrar a qualidade do majorante e minorante propostos.

Let T be the independence family of a matroid on N = {l,...,n} and let B denote the incidence vectors of its bases. The matroidal knapsack problem is the problem of finding z = max{cx : x € V}, where V = {x G {0, l}n : ax < b, x G B), a = (a\,... ,an) is a nonnegative integer vector and 6 > 0 is an integer. Problems belonging to this class, such as the multiple choice knapsack or the capacitated minimal spanning tree, are known to be jVP-complete. However, there are some instances that are easy to solve, say when {x G {0, l}n : ax < b} is a matroid on N. If it is not the case, it is shown how to compute polynomiaily an upper bound of z. It begins by proving that there exists a valid inequality for V, which is a matroidal relaxation for the knapsack constraint. Then, this constraint is added to V, in order to build a strong lagrangean dual. Using a polyhedral description for the matroidal knapsacks, it is shown that this bound strictly dominates the linear relaxation one and it can be obtained in polynomial time. It is also studied a polynomial heuristic procedure to compute a feasi¬ble solution to the problem and a lower bound of z and finally, it is pre¬sented some computational experience in order to illustrate the quality of the bounds.