View
222
Download
3
Category
Preview:
Citation preview
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmos Branch-and-Bound Para oProblema da Clique Máxima
P. V. EufrásioAutor
R. C. CorrêaOrientador
Departamento de ComputaçãoUniversidade Federal do Ceará
21 de outubro de 2009
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
1 IntroduçãoDefinições e Motivações
2 Algoritmo GenéricoCaracterísticas GeraisCritério de RamificaçãoDetalhes a Considerar
3 Algoritmo 1Cálculo do UBRamificação
4 Algoritmo 2Cálculo do UB
5 Resultados
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Definições e Motivações
Cliques e Clique Máxima
Uma clique de um grafo G é um subgrafo de G que écompleto.
Uma clique com a maior quantidade de vértices é umaclique máxima de G.
A B C
D E
GF H
D
GF
D E
G H
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Definições e Motivações
Cliques e Clique Máxima
Uma clique de um grafo G é um subgrafo de G que écompleto.
Uma clique com a maior quantidade de vértices é umaclique máxima de G.
A B C
D E
GF H
D
GF
D E
G H
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Definições e Motivações
Cliques e Clique Máxima
Uma clique de um grafo G é um subgrafo de G que écompleto.Uma clique com a maior quantidade de vértices é umaclique máxima de G.
A B C
D E
GF H
D
GF
D E
G H
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Definições e Motivações
Cliques e Clique Máxima
Uma clique de um grafo G é um subgrafo de G que écompleto.Uma clique com a maior quantidade de vértices é umaclique máxima de G.
A B C
D E
GF H
D
GF
D E
G H
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Motivações
Por que determinar uma clique máxima por enumeração?
Modela diversos problemas reais.Subproblema de outros problemas em teoria dos grafos.NP-Difícil.Existe ε > 0 tal que é NP-Difícil aproximar com fator nε.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Motivações
Por que determinar uma clique máxima por enumeração?
Modela diversos problemas reais.
Subproblema de outros problemas em teoria dos grafos.NP-Difícil.Existe ε > 0 tal que é NP-Difícil aproximar com fator nε.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Motivações
Por que determinar uma clique máxima por enumeração?
Modela diversos problemas reais.Subproblema de outros problemas em teoria dos grafos.
NP-Difícil.Existe ε > 0 tal que é NP-Difícil aproximar com fator nε.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Motivações
Por que determinar uma clique máxima por enumeração?
Modela diversos problemas reais.Subproblema de outros problemas em teoria dos grafos.NP-Difícil.
Existe ε > 0 tal que é NP-Difícil aproximar com fator nε.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Motivações
Por que determinar uma clique máxima por enumeração?
Modela diversos problemas reais.Subproblema de outros problemas em teoria dos grafos.NP-Difícil.Existe ε > 0 tal que é NP-Difícil aproximar com fator nε.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmo Branch-and-Bound
Idéia geral:
Particionar o conjunto de soluções em subconjuntosdisjuntos.Combinar as soluções dos subproblemas para obter asolução do problema original.
Árvore de Enumeração:
Todo o espaço de soluções. Enorme!!
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmo Branch-and-Bound
Idéia geral:Particionar o conjunto de soluções em subconjuntosdisjuntos.
Combinar as soluções dos subproblemas para obter asolução do problema original.
Árvore de Enumeração:
Todo o espaço de soluções. Enorme!!
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmo Branch-and-Bound
Idéia geral:Particionar o conjunto de soluções em subconjuntosdisjuntos.Combinar as soluções dos subproblemas para obter asolução do problema original.
Árvore de Enumeração:
Todo o espaço de soluções. Enorme!!
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmo Branch-and-Bound
Idéia geral:Particionar o conjunto de soluções em subconjuntosdisjuntos.Combinar as soluções dos subproblemas para obter asolução do problema original.
Árvore de Enumeração:Todo o espaço de soluções. Enorme!!
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Algoritmo Branch-and-Bound
Idéia geral:Particionar o conjunto de soluções em subconjuntosdisjuntos.Combinar as soluções dos subproblemas para obter asolução do problema original.
Árvore de Enumeração:Todo o espaço de soluções. Enorme!!
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
S
S1 ... Si ... Sn
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Características Gerais
Algoritmo Genérico
Percorre árvore de enumeração.
Mantém o tamanho da melhor solução já encontrada. LBCalcula o máximo que um novo nó pode ajudar na soluçãoótima. UBDescarta nós tais que UB < LB. PrunningRamifica os demais. Branching
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Características Gerais
Algoritmo Genérico
Percorre árvore de enumeração.Mantém o tamanho da melhor solução já encontrada. LB
Calcula o máximo que um novo nó pode ajudar na soluçãoótima. UBDescarta nós tais que UB < LB. PrunningRamifica os demais. Branching
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Características Gerais
Algoritmo Genérico
Percorre árvore de enumeração.Mantém o tamanho da melhor solução já encontrada. LBCalcula o máximo que um novo nó pode ajudar na soluçãoótima. UB
Descarta nós tais que UB < LB. PrunningRamifica os demais. Branching
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Características Gerais
Algoritmo Genérico
Percorre árvore de enumeração.Mantém o tamanho da melhor solução já encontrada. LBCalcula o máximo que um novo nó pode ajudar na soluçãoótima. UBDescarta nós tais que UB < LB. Prunning
Ramifica os demais. Branching
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Características Gerais
Algoritmo Genérico
Percorre árvore de enumeração.Mantém o tamanho da melhor solução já encontrada. LBCalcula o máximo que um novo nó pode ajudar na soluçãoótima. UBDescarta nós tais que UB < LB. PrunningRamifica os demais. Branching
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Critério de Ramificação
Algoritmo Genérico
Si = N(i)⋂{i + 1, ...,n} , i = 1, ...,n
S
S1
v1
... Si
vi
... Sn
vn
Precisamos ramificar cada vértice?
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Critério de Ramificação
Algoritmo Genérico
Si = N(i)⋂{i + 1, ...,n} , i = 1, ...,n
S
S1
v1
... Si
vi
... Sn
vn
Precisamos ramificar cada vértice?
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Critério de Ramificação
Algoritmo Genérico
Si = N(i)− {1, ..., i − 1} , i = 1, ...,p
����&%'$
&%'$
&%'$
&%'$,
,,,
,,
ll
ll
ll
S′
Sv1 v2 ...vp
v1 vi vp
UB(S′) = LB
S1 Si Sp
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Detalhes a Considerar
Algoritmo Genérico
LB Inicial
Cálculo do UB
Rápido, Pouco ApertadoLento, Bastante Apertado
Ordenação Inicial dos Vértices
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Detalhes a Considerar
Algoritmo Genérico
LB InicialCálculo do UB
Rápido, Pouco ApertadoLento, Bastante Apertado
Ordenação Inicial dos Vértices
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Detalhes a Considerar
Algoritmo Genérico
LB InicialCálculo do UB
Rápido, Pouco Apertado
Lento, Bastante Apertado
Ordenação Inicial dos Vértices
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Detalhes a Considerar
Algoritmo Genérico
LB InicialCálculo do UB
Rápido, Pouco ApertadoLento, Bastante Apertado
Ordenação Inicial dos Vértices
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Detalhes a Considerar
Algoritmo Genérico
LB InicialCálculo do UB
Rápido, Pouco ApertadoLento, Bastante Apertado
Ordenação Inicial dos Vértices
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 1
E. Tomita, T. Kameda, 2006. An efficientbranch-and-bound algorithm for finding a maximum cliquewith computational experiments.
Usa coloração gulosa para calcular o limite superior.
UB(S) = max {c | ∃v COR (v) = c}
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 1
E. Tomita, T. Kameda, 2006. An efficientbranch-and-bound algorithm for finding a maximum cliquewith computational experiments.Usa coloração gulosa para calcular o limite superior.
UB(S) = max {c | ∃v COR (v) = c}
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 1
E. Tomita, T. Kameda, 2006. An efficientbranch-and-bound algorithm for finding a maximum cliquewith computational experiments.Usa coloração gulosa para calcular o limite superior.
UB(S) = max {c | ∃v COR (v) = c}
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.
Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {} LB = 0
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {} LB = 0
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2} LB = 1
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2} LB = 1
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2} LB = 1
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2, v3} LB = 2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2, v3} LB = 2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2, v3} LB = 2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2, v3, v4} LB = 3
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Ramificação
Algoritmo 1
Ordena vértices por classe de cor.Ramifica primeiro os de classe mais alta.
v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7
v1 v2 v3 v4 v5 v6 v7
1 1 2 3 4 5 5
S′ = {v1, v2, v3, v4} LB = 3
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.
Encontra o conjunto independente máximo do grafocomplemento.Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.2 C: ciclos ímpares.3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.Encontra o conjunto independente máximo do grafocomplemento.
Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.2 C: ciclos ímpares.3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.Encontra o conjunto independente máximo do grafocomplemento.Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.2 C: ciclos ímpares.3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.Encontra o conjunto independente máximo do grafocomplemento.Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.
2 C: ciclos ímpares.3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.Encontra o conjunto independente máximo do grafocomplemento.Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.2 C: ciclos ímpares.
3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Algoritmo 2
E.C.Sewell, 1998. A Branch and Bound Algorithm for theStability Number of a Sparse Graph.Encontra o conjunto independente máximo do grafocomplemento.Particiona S em três conjuntos:
1 K: cliques com mais de 3 vértices.2 C: ciclos ímpares.3 V’: vértices restantes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Grafos de König
Grafo de Königα (G) = ρ (G)
Identidade de Gallaiυ (G) + ρ (G) = |V |
α (G) = |V | − υ (G)⇔ G é König
UB(S) = |K |+ (|V ′| − |M|) +∑
(|C| − 1) /2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Grafos de König
Grafo de Königα (G) = ρ (G)
Identidade de Gallaiυ (G) + ρ (G) = |V |
α (G) = |V | − υ (G)⇔ G é König
UB(S) = |K |+ (|V ′| − |M|) +∑
(|C| − 1) /2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Grafos de König
Grafo de Königα (G) = ρ (G)
Identidade de Gallaiυ (G) + ρ (G) = |V |
α (G) = |V | − υ (G)⇔ G é König
UB(S) = |K |+ (|V ′| − |M|) +∑
(|C| − 1) /2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Cálculo do UB
Grafos de König
Grafo de Königα (G) = ρ (G)
Identidade de Gallaiυ (G) + ρ (G) = |V |
α (G) = |V | − υ (G)⇔ G é König
UB(S) = |K |+ (|V ′| − |M|) +∑
(|C| − 1) /2
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Grafos Aleatórios
Instance MCR COCRG n ω(G) Nodes Time Nodes Time
(density)
100− 10 100 (0.10) 4 100 0 7 0200− 10 200 (0.10) 5 204 0 10 0100− 30 100 (0.30) 6 138 0 20 0200− 30 200 (0.30) 7 849 0 85 0100− 50 100 (0.50) 9 494 0 89 0200− 50 200 (0.50) 11 8.584 0 1.443 0100− 70 100 (0.70) 15 2.635 0 1.374 0200− 70 200 (0.70) 18 230.116 10 93.841 6100− 90 100 (0.90) 31 12.331 1 376.343 26200− 90 200 (0.90) 42 96.279.819 23.063 212.522.490 33.527
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
DIMACS Benchmark
Instance MCR COCRG n ω(G) Nodes Time Nodes Time
(density)
c-fat500-1 500 (0.036) 14 487 0 1.374 0c-fat500-2 500 (0.073) 26 475 1 172 0c-fat200-1 200 (0.077) 12 189 0 48 0c-fat200-2 200 (0.163) 24 177 0 88 0c-fat500-5 500 (0.186) 64 437 0 543 0c-fat500-10 500 (0.374) 126 375 1 1.348 4c-fat200-5 200 (0.426) 58 143 0 235 0brock200-2 200 (0.500) 12 4.162 0 509 0brock200-3 200 (0.605) 15 17.888 1 509 2brock200-4 200 (0.660) 17 72.999 3 16.598 2brock200-1 200 (0.750) 21 512.946 38 273.456 43brock400-2 400 (0.750) 29 114.439.396 13.930 98.544.980 16.750brock400-3 400 (0.750) 31 235.969.864 27.395 199.143.755 33.547brock400-1 400 (0.750) 27 323.039.745 44.263 126.393.547 19.889
gen200-p0.9-44 200 (0.900) 44 367.274 155 154.655.871 21.563gen200-p0.9-55 200 (0.900) 55 803.983 265 2.515.770 434
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Conclusão
Para instâncias difíceis, ambas as abordagensmostram-se ineficientes.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Trabalhos Futuros
Usar heurísticas para encontrar um bom LB inicial.
Estudar a relação da densidade com a eficiência de cadaalgoritmo.Paralelizar a solução dos subproblemas.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Trabalhos Futuros
Usar heurísticas para encontrar um bom LB inicial.Estudar a relação da densidade com a eficiência de cadaalgoritmo.
Paralelizar a solução dos subproblemas.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Trabalhos Futuros
Usar heurísticas para encontrar um bom LB inicial.Estudar a relação da densidade com a eficiência de cadaalgoritmo.Paralelizar a solução dos subproblemas.
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Perguntas?
?
Obrigado! ;)
Introdução Algoritmo Genérico Algoritmo 1 Algoritmo 2 Resultados
Perguntas?
?Obrigado! ;)
Recommended