XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: ALGORITHMS FOR OPTIMIZATION PROBLEMS APPLIED TO ROUTING AND WAVELENGTH ASSIGNMENT Autor: THIAGO FERREIRA DE NORONHA
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
CELSO DA CRUZ CARNEIRO RIBEIRO - ADVISOR
CARLOS JOSE PEREIRA DE LUCENA - CO-ADVISOR
Nº do Conteudo: 13749
Catalogação: 08/06/2009 Idioma(s): PORTUGUESE - BRAZIL
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@2
Resumo:
Título: ALGORITHMS FOR OPTIMIZATION PROBLEMS APPLIED TO ROUTING AND WAVELENGTH ASSIGNMENT Autor: THIAGO FERREIRA DE NORONHA
CARLOS JOSE PEREIRA DE LUCENA - CO-ADVISOR
Nº do Conteudo: 13749
Catalogação: 08/06/2009 Idioma(s): PORTUGUESE - BRAZIL
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@2
Resumo:
The problem of routing and wavelength assignment in WDM optical networks
consists in routing a set of lightpaths and assigning a wavelength
to each of them, such that lightpaths whose routes share a common fiber
are assigned to different wavelengths. The objective is to minimize the total
number of wavelengths used for routing all connections. This problem is called
min-RWA and was shown to be NP-hard. In this thesis, we first propose
efficient implementations of the state-of-art heuristics in the literature and
reevaluate them on a broader set of test instances. Following, we propose
a random-keys genetic algorithm for min-RWA. This algorithm extends the
best heuristic in the literature by embedding it into an evolutionary framework.
Computational results showed that the new heuristic improves the
state-of-the-art algorithms in the literature even when they were close to
the optimal solution. Finally, we propose a branch-and-cut algorithm for the
Partition Coloring Problem (PCP), which is a generalization of the graph
coloring problem. Algorithms for PCP have been used in the literature as
building blocks for algorithms for min-RWA. An integer programming formulation,
valid inequalities, and a cutting plane procedure are proposed.
Computational experiments are reported for random graphs and for PCP
instances originating from min-RWA instances.
Descrição | Arquivo |
COVER, ACKNOWLEDGEMENTS, RESUMO, ABSTRACT, SUMMARY AND LISTS | |
CHAPTER 1 | |
CHAPTER 2 | |
CHAPTER 3 | |
CHAPTER 4 | |
CHAPTER 5 | |
CHAPTER 6 | |
REFERENCES |