Uma Metaheurística VNS
aplicada ao Problema do Maior
Conjunto Controlado
Ivairton Monteiro Santos - UFF
Carlos Alberto Martinhon - UFF
Luis Satoru Ochi - UFF
Tópicos








Conceitos básicos do problema
Problema da Verificação de Monopólio - PVM
Problema do Maior Conjunto Controlado - PMCC
Regras de redução
Algoritmo de Makino et al. [2002]
VNS/VND aplicados ao PMCC
Resultados obtidos
Trabalhos futuros
Definição do Problema:
Conceitos Básicos
Considerando um grafo não orientado G=(V,E) e M  V
 Definição 1: Vizinhança de um vértice v V


NG[v] = {w V | (w, v)  E} U {v}
Definição 2: Um vértice v é controlado por M  V 

|NG[v]M|  |NG[v]|/2
Exemplo:
Não Controlado
Controlado
Problema da Verificação de Monopólio PVM (Makino et al.[2002])

Considere:
G1=(V, E1) e G2=(V, E2), tal que E1  E2 e M  V

Questão:

 G=(V, E) tal que E1  E  E2 e M seja monopólio em G ?
G2=(V,E2)
 

Complexidade Polinomial: Õ min (n  m2 )3/ 2 ,n3/ 2 (n  m2 )
Problema do Maior Conjunto
Controlado


Se o problema de monopólio retorna “NÃO”, então
tenta-se controlar o maior número de vértices possíveis.
Problema NP-Difícil [Makino et al. 2002]
Não Controlado
Controlado
Regras de Redução
Exemplo:
Nunca Controlado
Indefinido
Sempre Controlado
Regras de Redução
Nunca Controlado
Indefinido
Sempre Controlado
Regras de Redução
As regras de redução visam reduzir o número de arestas optativas.
1 ou 0
1
0
? – Espaço de busca
Algoritmo de Makino et al. [2002]
Heurística MYK
0,5-aproximada
Não Controlado
Controlado
Variable Neighborhood Descent
VND


O VND e VNS buscam encontrar ótimos locais
variando suas estruturas de vizinhança.
Estruturas de Vizinhanças

NXY
X = número de vértices a serem descontrolados
Y = número de vértices a serem controlados
Y>X

Exemplos:


N0Y = Controlar pelo menos 1 vértice, sem descontrolar
nenhum.
N1Y = Controlar pelo menos 2 vértices, descontrolando
apenas 1.
Estruturas de Vizinhança (cont.)
Vizinhança
N0Y
Vizinhança
N1Y
Não Controlado
Controlado
Alguns Resultados Computacionais
N. de Prob. Lim. Sup.
Vértices
Vértices
de
v M Controlados
0,25
490
500
0,3
499
0,4
499
0,25
967
1000
0,3
999
0,4
999
0,25
1499
1500
0,3
1499
0,4
1499
0,25
1889
2000
0,3
1999
0,4
1999
Regras deAlg. deMYKVND Aproximação
Redução
SC - NC
119 - 10
343
354
72,24%
166
333
461
93,89%
196
304
499
100,00%
241
667
679
70,21%
289
710
833
83,38%
405
594
999
100,00%
412 1087 1212
80,85%
447 1052 1275
85,05%
589
910 1499
100,00%
364 1135 1142
60,45%
612 1387 1733
86,69%
828 1171 1999
100,00%
Trabalhos Futuros




Apresentar uma extensão do problema, considerando-se
pesos distintos p/ cada nó.
Implementar novas estratégias p/ determinação de boas
soluções iniciais.
Inserir novas estrut. de vizinhança (p/ VNS e VND)
Comparar c/ heurística (Martinhon&Protti[2003])
1 1  y*
Razão   *
2 2y  2
onde y* é o valor da Relax. Linear