20755Problema da árvore...Moura, Pedro Martins, 1971-ing1713ulsd11jan2010/1VIEWcriticalOAI-RUL2010-01-11 16:27:11creator:MARTA2010-01-11 16:40:16viewer:internalDUL0124170 descriptivedc por info:eu-repo/semantics/doctoralThesis application/pdf Problema da árvore de suporte de custo mínimo com restrição de grau e custos associados aos nodos Tese de doutoramento, Estatística e Investigação Operacional (Optimização), 2009, Universidade de Lisboa, Faculdade de Ciências Nesta dissertação aborda-se uma variante de Problemas de Árvores em Grafos onde, para além de custos associados às ligações entre os nodos, existem também custos associados ao grau dos nodos. Esta variante é motivada no contexto de redes de telecomunicações, onde estes custos se encontram associados a equipamento de routing que é necessário instalar em todo os nodos que estejam ligados a mais do que um nodo na rede. Neste tipo de redes é ainda usual restringir o número máximo de ligações de cada vértice de forma a reduzir interferências de sinal. Esta variante é aplicada a dois problemas clássicos de Árvores em Grafos: o problema da Árvore de Suporte de Custo Mínimo e o problema da Árvore de Steiner com Recolha de Prémios. Incorporando esta variante nas formulações tradicionalmente utilizadas para estes problemas chega-se a modelos não lineares, devido à presença dos custos associados ao grau dos vértices. Duas técnicas de reformulação de modelos s˜aoent˜ao utilizadas: a técnica de Reformulação por Discretização e a técnica de Reformulação por Caminhos. Ao utilizar qualquer uma destas duas técnicas no modelos tradicionais, obtˆem-se modelos lineares. Além disso, as duas técnicas permitem construir conjuntos de desigualdades válidas que ao ser adicionadas a um modelo fortalecem-no no que diz respeito à respectiva relaxação linear. A segunda técnica só pode ser aplicada ao primeiro problema devido à existência de uma estrutura de Saco Mochila, presente neste problema. Os modelos apresentados são comparados utilizando um conjunto de instâncias com 25 e 50 nodos. open access Árvores (Matemática) Investigação operacional Teses de doutoramento Moura, Pedro Martins, 1971- Gouveia, Luís, 1957- 2009 http://catalogo.ul.pt/F/?func=item-global&doc_library=ULB01&type=03&doc_number=000569932In this dissertation a new variant of Tree Problems in Graphs is considered.In this variant, besides the costs associated to the links between the nodes,there also exist costs associated with the degree of the nodes. This variantis motivated in the context of telecommunications networks where this typeof costs is associated with routing equipment that has to be installed inevery node that is connected with more than one node in the network. Inthis kind of networks it is usual to limit the number of links in any node toprevent signal interferences. This variant is applied to two classical problems:the Spanning Tree Problem and the Prize-collecting Steiner Tree Problem.By integrating this variant in traditional formulations for these problem oneobtains non-linear models, due to the presence of the costs associated withthe degree of the nodes. Two reformulations techniques are then used: theReformulation by Discretization technique and the Reformulation by Pathstechnique. Linear models are obtained by using any of these two techniquesin the traditional models. In addition, different sets of valid inequalities canbe constructed with the use of these techniques which, when added to amodel, strengthen it in terms of the respective linear relaxation. The secondtechnique can only be applied to the first problem due to the existence of aKnapsack structure present in this problem.The presented models are compared using a set of instances with 25 and 50nodes.]]>24174technicaltext_md 1163573 CRC32 17e13b93 MD5 35211be16d628f6cf449f880a8fae43f SHA-1 2bbf28edad4f3a734252db58011e144bc76f6abe application/pdf ]]>24175changehistorychangehistory_mdServiceTechnicalMetadataExtractorTechnical Metadata Extraction2010-01-11T16:29:07.145ZAdd some metadata to the digital entity using jhovesoftware_usedJHove]]>20755_ulsd057582_td.pdfpdfapplication/pdf/digitool_storage/deposit-master/2010/01/11/file_1/207551006-11163573