Thiago Ferreira de Noronha
PUC-Rio - Certificação Digital Nº 0410880/CA
Algoritmos para Problemas de Otimização
Aplicados a Roteamento e Atribuição de
Comprimentos de Onda
Tese de Doutorado
Tese apresentada ao Programa de Pós–graduação em Informática
do Departamento de Informática da PUC–Rio como requisito
parcial para obtenção do tı́tulo de Doutor em Informática.
Orientadores: Prof. Celso da Cruz Carneiro Ribeiro
Prof. Carlos José Pereira de Lucena
Rio de Janeiro
Setembro de 2008
Thiago Ferreira de Noronha
PUC-Rio - Certificação Digital Nº 0410880/CA
Algoritmos para Problemas de Otimização
Aplicados a Roteamento e Atribuição de
Comprimentos de Onda
Tese apresentada ao Programa de Pós–graduação em Informática
do Departamento de Informática do Centro Técnico Cientı́fico
da PUC–Rio como requisito parcial para obtenção Do tı́tulo de
Doutor em Informática. Aprovada pela Comissão Examinadora
abaixo assinada.
Prof. Celso da Cruz Carneiro Ribeiro
Orientador
Universidade Federal Fluminense
Prof. Carlos José Pereira de Lucena
Presidente
Pontifı́cia Universidade Católica do Rio de Janeiro
Prof. Cid Carvalho de Souza
Universidade Estadual de Campinas
Prof. Edward Hermann Haeusler
Pontifı́cia Universidade Católica do Rio de Janeiro
Prof. Luciana Salete Buriol
Universidade Federal do Rio Grande do Sul
Prof. Simone de Lima Martins
Universidade Federal Fluminense
Prof. José Eugenio Leal
Coordenador Setorial do Centro Técnico Cientı́fico — PUC–Rio
Rio de Janeiro, 05 de Setembro de 2008
Todos os direitos reservados. É proibida a reprodução total
ou parcial do trabalho sem autorização da universidade, do
autor e do orientador.
Thiago Ferreira de Noronha
PUC-Rio - Certificação Digital Nº 0410880/CA
Possui graduação em Ciências da Computação pela Universidade Federal do Rio Grande do Norte (2001) e mestrado em Informática pela Pontifı́cia Universidade Católica
do Rio de Janeiro (2004). Tem experiência na área de Ciência
da Computação, com ênfase em Otimização Combinatória,
atuando principalmente nos seguintes temas: metaheurı́sticas,
programação matemática e otimização combinatória.
Ficha Catalográfica
Noronha, Thiago Ferreira de
Algoritmos para Problemas de Otimização Aplicados a
Roteamento e Atribuição de Comprimentos de Onda / Thiago
Ferreira de Noronha; orientador: Celso da Cruz Carneiro Ribeiro; co–orientador: Carlos José Pereira de Lucena. — 2008.
89 f.: il. ; 30 cm
1. Tese (Doutorado em Infomática) - Pontifı́cia Universidade Católica do Rio de Janeiro, Departamento de Informática, 2008.
Inclui referências bibliográficas.
1. Informática – Tese. 2. Otimização Combinatória. 3.
Heurı́sticas. 4. Algoritmos exatos. 5. Roteamento e atribuição de comprimentos de onda. I. Ribeiro, Celso. II. Lucena, Carlos. III. Pontifı́cia Universidade Católica do Rio de
Janeiro. Departamento de Informática. IV. Tı́tulo.
CDD: 004
PUC-Rio - Certificação Digital Nº 0410880/CA
Agradecimentos
À minha esposa Luzia Sergina de França Neta pelo amor, carinho e
compreensão.
À minha mãe, irmãs e famı́lia por terem me incentivado a lutar por este
sonho, mesmo sofrendo com minha ausência.
Aos meus orientadores, pelo apoio e incentivo para a realização deste
trabalho.
Aos meus colegas da PUC–Rio, que sempre me incentivaram e me
apoiaram.
Aos funcionários do departamento de Informática, pela ajuda de todos
os dias.
Ao CNPq e à PUC–Rio, pelos auxı́lios concedidos, sem os quais este
trabalho não poderia ter sido realizado.
Resumo
PUC-Rio - Certificação Digital Nº 0410880/CA
Noronha, Thiago Ferreira de; Ribeiro, Celso; Lucena, Carlos. Algoritmos para Problemas de Otimização Aplicados a Roteamento e Atribuição de Comprimentos de Onda. Rio de
Janeiro, 2008. 89p. Tese de Doutorado — Departamento de Informática, Pontifı́cia Universidade Católica do Rio de Janeiro.
O problema de roteamento e atribuição de comprimentos de onda em
redes óticas WDM consiste em rotear um conjunto de caminhos óticos
e atribuir um comprimento de onda para cada um deles de modo que
dois caminhos óticos cujas rotas compartilham alguma fibra ótica tenham
comprimentos de onda diferentes. O objetivo é minimizar o número total de
comprimentos de onda utilizados para rotear todos os caminhos óticos. Este
problema é conhecido na literatura como min-RWA e está provado que ele
pertence à classe dos problemas NP-Difı́ceis. Primeiramente, são propostos
nesta tese algoritmos e estruturas de dados que permitem a implementação
eficiente das melhores heurı́sticas na literatura. Em seguida propõe-se um
algoritmo genético com chaves aleatórias para min-RWA. Este algoritmo
estende a melhor heurı́stica na literatura adaptando-a a um paradigma
evolucionário. Por fim, propõe-se um algoritmo de Branch-and-Cut para
o problema de coloração de partições (PCP), o qual é uma generalização do
problema de coloração de grafos. Algoritmo para PCP vem sendo usados na
literatura como ferramentas para construção de algoritmos para min-RWA.
São propostas uma formulação por programação linear inteira para PCP,
desigualdades válidas e um algoritmo de planos de corte. Experimentos
computacionais são apresentados para instâncias em grafos aleatórios e
instâncias de PCP originadas de instâncias de min-RWA.
Palavras–chave
Otimização Combinatória. Heurı́sticas.
teamento e atribuição de comprimentos de onda.
Algoritmos exatos.
Ro-
Abstract
PUC-Rio - Certificação Digital Nº 0410880/CA
Noronha, Thiago Ferreira de; Ribeiro, Celso; Lucena, Carlos. Algorithms for Optimization Problems Applied to Routing and
Wavelength Assignment. Rio de Janeiro, 2008. 89p. PhD Thesis
— Department of Informática, Pontifı́cia Universidade Católica do
Rio de Janeiro.
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.
Keywords
Optimization problems.
wavelength assignment.
Heuristics.
Branch-and-Cut.
Routing and
Sumário
PUC-Rio - Certificação Digital Nº 0410880/CA
1
Introdução
11
2 Trabalhos Relacionados
2.1 Heurı́stica de Bannerjee e Mukherjee
2.2 Heurı́stica de Hyytiä e Virtamo
2.3 Heurı́stica de Li e Simha
2.4 Heurı́stica de Manohar, Manjunath e Shevgaonkar
2.5 Heurı́stica de Noronha e Ribeiro
2.6 Heurı́stica de Skorin-Kapov
15
15
17
19
21
23
26
3 Implementação Eficiente das Heurı́sticas para min-RWA
3.1 Análise da Complexidade Computacional
3.2 Implementações Avançadas
3.3 Heurı́stica de Multi-partida para min-RWA
3.4 Experimentos Computacionais
29
29
31
34
34
4 Algoritmo Genético com Chaves Aleatórias
4.1 Visão Geral
4.2 Algoritmo Genético para min-RWA
4.3 Framework para Algoritmos Genéticos com Chaves Aleatórias
4.4 Experimentos Computacionais
44
44
45
46
48
5 Algoritmo Exato para Coloração de Partições
5.1 Algoritmos para Coloração de Grafos
5.2 Formulação por Representantes para Coloração de Partições
5.3 Branch-and-cut para Coloração de Partições
5.4 Experimentos Computacionais
57
57
59
62
70
6
79
Conclusões
Referências Bibliográficas
81
Lista de figuras
1.1
(a) Grafo particionado e (b) sua coloração ótima com duas cores.
13
2.1
2.2
2.3
2.4
2.5
2.6
Formulação do problema de roteamento.
Pseudocódigo do procedimento BGAforEDP.
Pseudocódigo do procedimento Greedy-EDP-RWA.
Pseudocódigo do procedimento k-EDR.
Pseudocódigo do procedimento TS-PCP.
Pseudocódigo das heurı́sticas FF-RWA e BF-RWA.
16
22
23
24
26
28
PUC-Rio - Certificação Digital Nº 0410880/CA
3.1
3.2
Exemplo de uma topologia em grade 3 × 4.
(a) Desvios relativos médios e (b) tempos de execução médios
(em segundos) de FF-RWAST D , BF-RWAST D , FFD-RWAST D e
BFD-RWAST D sobre as 187 instâncias.
3.3 Média dos tempos de execução de (a) FF-RWAN RRt , (b)
FFD-RWAN RRt , (c) BF-RWAN RRt e (d) BFD-RWAN RRt nos conjuntos de instâncias K, Y , Z e W . Os tempos são apresentados
como um desvio percentual dos tempos de BF-RWAST D .
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
5.1
5.2
5.3
5.4
5.5
Ilustração do processo de transição entre gerações sucessivas.
Diagrama de classes do framework para algoritmos genéticos com
chaves aleatórias.
Exemplo de aplicação do framework de algoritmos genéticos para
min-RWA.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância Y.5.80.1.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância Y.5.100.2.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância Z.4x25.60.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância Z.10x10.20.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância ATT.
Distribuição empı́rica de probabilidade das heurı́sticas MS-BFD e
GA-RWA atingirem o alvo para a instância ATT2.
Decomposição do PCP sobre o grafo GP em dois subproblemas de
coloração de partições definidos sobre os grafos G1 e G2 .
(a) Conjunto particionado e (b) Conjunto independente particionado.
Grafo com os respectivos valores de h.
Média dos limites inferiores e superiores para o número ótimo de
cores variando-se o número de vértices.
Média dos limites inferiores e superiores para o número ótimo de
cores variando-se a densidade das arestas.
36
37
40
45
48
49
52
52
53
53
54
54
64
65
69
71
72
Lista de tabelas
3.1
3.2
3.3
3.4
PUC-Rio - Certificação Digital Nº 0410880/CA
3.5
Desvios relativos médios e tempos de execução médios (em segundos) de FF-RWAST D , BF-RWAST D , FFD-RWAST D e BFD-RWAST D para
as instâncias dos conjuntos K, Y , Z e W .
Média dos tempos de execução das diferentes implementações das
heurı́sticas FF-RWA, FFD-RWA, BF-RWA e BFD-RWA nos conjuntos
de instâncias K, Y , Z e W . Os tempos são apresentados como o
desvio percentual em relação aos tempos das respectivas heurı́sticas
implementadas com STD.
Resultados computacionais de BFD-RWA e MS-BFD para o conjunto
de instâncias Y .
Resultados computacionais de BFD-RWA e MS-BFD para o conjunto
de instâncias Z.
Resultados computacionais de BFD-RWA e MS-BFD para o conjunto
de instâncias W .
Tempos médios obtidos por MS-BFD e diferentes versões de GA-RWA
para encontrar uma solução com custo tão bom quanto o alvo.
4.2 Desvio relativo das soluções encontradas por GA-RWA e
2-EDR+TS-PCP em 10 minutos de execução.
37
39
41
42
43
4.1
5.1
5.2
5.3
5.4
5.5
Número de instâncias resolvidas exatamente em duas horas de
processamento para diferentes valores da densidade de arestas.
Contribuição dos cortes externos e internos a relaxação linear.
Instâncias de coloração de vértices.
Resultados computacionais para instâncias de min-RWA associadas
a três redes com topologia em anel.
Resultados computacionais para instâncias de RWA associadas com
a rede NSFnet.
51
56
73
74
75
77
78
PUC-Rio - Certificação Digital Nº 0410880/CA
Ciência da computação tem tanto a ver com
o computador como a Astronomia com o
telescópio, a Biologia com o microscópio, ou
a Quı́mica com os tubos de ensaio. A Ciência
não estuda ferramentas, mas o que fazemos e
o que descobrimos com elas.
Edsger Dijkstra.