Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/2855
Título: Mochilas Matroidais
Autor: Amado, Lígia
Orientador: Bárcia, Paulo
Palavras-chave: mochila
matroide
relaxação
dual
complexidade
heurística
knapsack
matroid
relaxation
dual
complexity
heuristic
Data de Defesa: Jun-1997
Editora: Instituto Superior de Economia e Gestão
Citação: Amado, Lígia. 1997. "Mochilas Matroidais". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão
Resumo: 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.
Descrição: Doutoramento em Matemática Aplicada à Economia e Gestão
URI: http://hdl.handle.net/10400.5/2855
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
TD-LDBA-1997.pdf25,05 MBAdobe PDFVer/Abrir    Acesso Restrito. Solicitar cópia ao autor!


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.