O PROBLEMA DA PSEUDO ÁRVORE CAPACITADA DE
CUSTO MÍNIMO
Guilherme Figueiredo Terenciani1 , Edna Hoshino1
1
Faculdade de Computação FACOM – Universidade Federal de Mato Grosso do Sul (UFMS)
CEP: 79070-900 - Caixa Postal 549 Campo Grande/MS - Brasil
Resumo. Este trabalho apresenta o problema da pseudo árvore capacitada de
custo mı́nimo e propõe uma heurı́stica para encontrar pseudo árvores capacitadas baseada em heurı́sticas de problemas relacionados, como o problema da
árvore de Steiner [Hwang et al. 1992] e o problema dos anéis-estrelas capacitados. O problema estudado surge como um subproblema de pricing de um
modelo baseado em cobertura de conjuntos para um problema mais geral denominado o problema das m pseudo árvores capacitadas. Trabalhos anteriores
mostram que a relaxação linear deste modelo fornece bons limitantes inferiores,
mas a solução exata do subproblema de pricing exige alto custo de processamento, o qual motiva o estudo de boas heurı́sticas para se resolver o problema.
Testes computacionais foram realizados para avaliar a qualidade das soluções
geradas pela heurı́stica proposta. Os resultados mostram que, na média, os
limitantes gerados estão aproximadamente 14% distantes do ótimo. Futuramente, pretende-se incorporar a heurı́stica aqui proposta como uma heurı́stica
de pricing dentro de um algoritmo branch-and-price para o problema das m
pseudo árvores capacitadas.
1. Introdução
Este trabalho propõe uma heurı́stica para o problema da pseudo árvore capacitada de custo mı́nimo (CRTP), que surge como um subproblema de pricing de modelos
baseados em cobertura de conjuntos para o problema das m pseudo árvores capacitadas.
Trabalhos anteriores mostram que a relaxação linear destes modelos fornecem bons limitantes inferiores, mas a solução exata do subproblema de pricing exige alto custo de
processamento, o qual motiva o estudo de boas heurı́sticas para o subproblema. Dado um
grafo G = (V, E), uma pseudo árvore é um subgrafo conexo de G contendo no máximo
um ciclo. Dados uma partição de V em ({d}, U1 , U2 , W ) e um inteiro Q, uma pseudo
árvore T = (VT , ET ) de G é válida se (i) T é uma árvore com exatamente uma aresta
incidente em d e VT ∩ U2 = ∅; ou (ii) T contém um ciclo C tal que vértices em U2 pertencem a VT somente se ocorrem no único ciclo C, que necessariamente deve conter d;
e (iii) |VT ∩ (U1 ∪ U2 )| ≤ Q. Dado um grafo G = ({d} ∪ U1 ∪ U2 ∪ W, E), um inteiro
Q, pesos ce associados a cada aresta e ∈ E e prêmios pv em cada vértice v ∈ U1 ∪ U2 ,
oPCRTP consiste
P em encontrar uma pseudo árvore válida T = (VT , ET ) que minimiza
e∈ET ce −
v∈VT pv .
2. A heurı́stica proposta
Para a construção da heurı́stica foi utilizada a linguagem de programação C e
utilizada uma abordagem construtiva na qual atacamos o problema em partes a fim de ao
final obtermos o resultado esperado. Abaixo são apresentados os passos seguidos para a
construção da heurı́stica:
2.1. Construção da árvore geradora capacitada
Definição: Considere um grafo não direcionado G = (V, E) onde para cada aresta
e ∈ E, tem-se um custo Ce associado. Deseja-se encontrar um subconjunto T ⊆ E que
conecta todos os vértices de G e cuja soma total dos seus custos dado pela Equação 1 é
minimizada.
X
C(T ) =
Ce
(1)
e∈T
Para o fim da construção da árvore geradora capacitada, utilizamos o Algoritmo de
[Prim 1957] com algumas modificações para atender ao nosso problema geral. Onde
para o nosso problema T = (VT , ET ) é construı́da partindo-se de uma solução parcial
T = ({d}, ∅) e, sucessivamente, incluindo-se um vértice v em V \ VT que minimiza
cuv − pv , em que u ∈ VT , enquanto |VT ∩ (U1 ∪ U2 )| ≤ Q.
2.2. Construção da pseudo árvore
Com base na pseudo árvore proposta por [Hill and Voss 2015] o algoritmo criado para a construção da pseudo árvore tem como entrada uma árvore capacitada, gerada
por um algoritmo guloso baseado no Algoritmo de Prim, e devolve como saı́da a pseudo
árvore com apenas um ciclo contendo, pelo menos, o servidor e todos os clientes prioritários, evitando assim a perda de comunicação dos mesmos com o servidor.
O algoritmo usa uma abordagem construtiva para a construção do ciclo. O algoritmo começa servidor e percorre todos os outros vertices que pertencentes a arvore para
verificar de eles devem estar no ciclo ou não. Existem três possibilidades, (I) Não existe
nenhum vertice do tipo U2 portanto, a arvore é valida, (II) Momento quando partimos
do servidor e encontramos o primeiro vertice do tipo U2(e) é inserida uma aresta ligando
o vertice V(e) ao servidor construindo assim um ciclo e (III) Quando já temos o ciclo e
encontramos um vertice do tipo U2(e) que não esta contido no ciclo em que removemos
uma aresta contida no ciclo ligada ao seu antecessor U2(i) e incluimos a aresta A(e,i)
aumentando assim o tamanho do ciclo e fazendo com que o vertice V(e) seja incluido no
ciclo.
2.3. Two-Change
A técnica de aceleração Two-Change, utilizada para o problema TSP
[Croes 1958], pode ser facilmente adaptada para o problema da pseudo árvore, pelo fato
da pseudo árvore ter apenas um ciclo, podemos utiliza-lo para diminuir o custo da pseudo
árvore.
3. Resultados Computacionais
Os testes realizados nas instâncias computacionais foram motivadores, além do
tempo de execução da heurı́stica ser muito baixo, conseguimos bons resultados de custo
da pseudo árvore, mas devemos ter cuidado ao fazer tal afirmação, para confirmar a qualidade da heurı́stica proposta rodaremos o algoritmo exato para a construção da pseudo
árvore.
Para verificar a qualidade dos limitantes gerados pela heurı́stica, um algoritmo
exato baseado em branch-and-bound foi implementado usando a biblioteca GLPK e um
modelo de PLI para o problema. Após a construção do algoritmo exato para o problema
das peseudo árvores, comparamos a execução do algoritmo exato com os valores obtidos
pela heurı́stica. Como esperado, o valor ótimo (S*), obtido pelo algoritmo exato, é menor
do que aqueles obtidos pela heurı́sca, mas com um tempo de execução bem maior comparado aos tempos obtidos pela heurı́stica. O tempo do algoritmo exato chega a 134,9
segundos em instâncias fáceis, nas quais o número de vertices é de apenas 26, enquanto o
tempo gasto pela heurı́stica fica próximo de zero.
A Tabela 1 apresenta um resumo dos testes realizados para avaliar a qualidade da
solução gerada pela heurı́stica. Na tabela, os resultados estão agrupados pelo número de
vértices do grafo de entrada.
Tabela 1. Resumo comparativo da qualidade dos limitantes
total
100%
82,1%
tempo médio (em seg)
12,6
108
gap s/ 2-opt
18,2%
18,7%
gap c/ 2-opt
14.7%
17,7%
• tempo médio/s tempo médio gasto pelo algoritmo exato (em segundos);
• gap s/ 2-opt qualidade da solução gerada pela heurı́stica sem Two-Change;
• gap c/ 2-opt qualidade da solução gerada pela heurı́stica com Two-Change.
Como pode ser observado na Tabela 1, a heurı́stica mostrou-se muito eficaz nos
testes realizados quando comparado ao algoritmo exato. Analisando-se os resultados entre
o algoritmo exato e a heurı́stica em instâncias com 26 vértices, obtivemos um GAP médio
de apenas 14, 7% que demonstra que além da heurı́stica resolver o problema de forma
rápida ela também constrói soluções muito próximas às do algoritmo exato. As colunas
tempo médio e total mostram a dificuldade do algoritmo exato em resolver as instâncias
testes com 51 vértices.
4. Conclusões e trabalhos futuros
Testes preliminares mostraram a eficiência e agilidade da heurı́stica proposta neste
trabalho para a construção de pseudo árvores de custo mı́nimo. Testes adicionais em
instâncias mais complexas devem ser realizados para analisar o tempo gasto e os valores
obtidos em relação ao algoritmo exato, para então obter uma estimativa mais precisa da
qualidade da heurı́stica em relação ao algoritmo exato.
Futuramente, pretende-se incorporar a heurı́stica aqui proposta como uma
heurı́stica de pricing dentro de um algoritmo branch-and-price para o problema das m
pseudo árvores capacitadas, potencialmente reduzindo o tempo do algoritmo.
Referências
Croes, G. A. (1958). A method for solving traveling salesman problems. Operations
Research, 6:791–812.
Hill, A. and Voss, S. (2015). Optimal capacitated ring trees. EURO Journal on Computational Optimization, pages 1–30.
Hwang, F. K., Richards, D. S., and Winter, P. (1992). The Steiner tree problem. Elsevier.
Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System
Technical Journal, 36:1389–1401.