ALGORITMOS PARA O PROBLEMA NÃO CAPACITADO DE FLUXOS COM CUSTOS FIXOS NOS ARCOS:
UMA COMPARAÇÃO ESTATÍSTICA
1.Introdução
Os problemas de otimização em redes representam uma grande classe dentre os
problemas de otimização. Como característica fundamental tais problemas são
definidos em grafos G=(N,E) nos quais N representa o conjunto de nós e E, o
conjunto de arestas, i.e., pares de nós. Um grafo de pequeno tamanho está
representado na Figura_1. Neste caso, as arestas estão direcionadas e são
denominadas arcos. Este tipo de grafo é denominado dígrafo. Podemos observar a
presença de quatro nós, N={i,j,k,l}, e sete arcos, E={(i,j),(j,i),(i,k),(j,k),
(k,j),(k,l),(l,k)}. No dígrafo G=(N,E), os nós poderiam estar representando
quatro regiões de uma cidade e os arcos, as principais vias de acesso entre as
localidades.
O problema para cuja solução pretendemos apresentar e comparar algoritmos é o
chamado problema não capacitado de fluxos com custos fixos nos arcos, NCFCF
(Nemhauser & Wolsey, 1988). O problema NCFCF pertence à grande classe de
problemas de otimização em redes formando ele próprio uma subclasse bem
peculiar de modelos com muitas aplicações práticas de interesse. Para citar
apenas alguns poucos exemplos, esse modelo genérico tem aplicações em problemas
de planejamento de redes de distribuição, redes de transportes e de
telecomunicações. Leitores interessados podem encontrar maiores detalhes em
Cruz et al. (1994, 1998).
No problema NCFCF, estão envolvidos custos de utilização dos arcos e custos
dependentes do montante de fluxo suportado pelo arco. O objetivo é determinar
uma combinação de arcos com custo total mínimo (custos de utilização mais
custos dependentes) que conduza os fluxos dos nós de oferta a todos os nós de
demanda possivelmente passando por nós intermediários de transbordo, também
conhecidos como nós de Steiner. Este é claramente um problema de otimização da
classe NP-árdua (do inglês NP-hard), uma vez que generaliza entre outros o
conhecido problema de Steiner em grafos (Maculan, 1987), que é NP-árduo (Garey
& Johnson, 1979). De fato, a prova da sua NP-complexidade pode ser
facilmente desenvolvida (Cruz et al., 1994).
Um problema NCFCF definido sobre o dígrafo da Figura_1 poderia ter o seguinte
enunciado. Quais seriam as estradas (arcos) a serem recuperadas, para escoar a
produção da região i até os centros consumidores representados pelas regiões j
e l gastando o mínimo possível? Supomos existir um custo fixo associado à
escolha da estrada, representando obras de infra-estrutura, e um custo variável
de utilização da estrada, representando obras de manutenção. A Figura_2 ilustra
uma solução para o problema que pode ser a ótima dependendo dos custos fixos e
variáveis considerados.
Um dos problemas mais recorrentes na área de desenvolvimento de algoritmos é o
de compará-los e classificá-los adequadamente. Freqüentemente, há restrições de
custo/tempo e um número infinito de possíveis instâncias de teste. Há também
uma variabilidade intrínseca ao processo de aquisição de algumas medidas de
desempenho (e.g. tempo de processamento). Surge daí a necessidade do uso de
alguma ferramenta estatística. O nosso interesse se concentra especificamente
na comparação de algoritmos para o problema NCFCF para o qual certamente tal
dificuldade não poderia deixar de ocorrer. Entretanto, esta deve ser também a
preocupação de desenvolvedores de algoritmos para outras finalidades.
A comparação de vários algoritmos (tratamentos) com relação a uma medida de
desempenho (resposta) envolve um estudo experimental e a análise estatística
dos dados resultantes, pois há um número infinito de instâncias passíveis de
ser consideradas e mesmo em computadores existe variação entre as medidas de
desempenho de programas de execução para execução. Experimentar com alocação
aleatória dos "tratamentos" às execuções é então útil para gerar as
distribuições necessárias às comparações necessariamente feitas com
estatística.
Em estudos envolvendo algoritmos, é razoável que se considerem classes de
problemas e que instâncias destas classes venham a ser resolvidas por todos os
algoritmos sob estudo. O experimento correspondente consta de duas
aleatorizações. Uma é sobre as classes de problemas, ou seja, são escolhidas
aleatoriamente instâncias de uma determinada classe. A outra, dada uma
instância de determinada classe, é feita selecionando-se a ordem de aplicação
dos algoritmos. Este planejamento é descrito por Neter et al. (1990) como
experimento a dois fatores com medidas repetidas em um dos fatores e vem sendo
utilizado com freqüência em várias áreas como biologia, engenharia e ciências
sociais. Na comparação de algoritmos para o problema NCFCF, será considerado um
estudo experimental com dois fatores (classes de problemas e algoritmos) com
medidas repetidas no fator algoritmos.
Este artigo está organizado do seguinte modo. Na Seção 2, apresentamos mais
detalhadamente o problema NCFCF. Formalizamos o problema NCFCF como um modelo
de programação matemática inteira mista e apresentamos os algoritmos para a sua
resolução. A Seção 3 é dedicada à apresentação dos resultados obtidos cuja
análise e discussão se encontram na Seção 4. Finalmente, a Seção 5 é dedicada
às conclusões finais.
2. Formulação do Problema NCFCF e Algoritmos
2.1 Modelo Matemático
É muito importante formalizar matematicamente o problema NCFCF, pois os
algoritmos de resolução são derivados diretamente da sua formulação. Um modelo
de programação matemática inteira mista típica para o problema (Rardin &
Wolsey, 1993) definida sobre o grafo direcionado G=(N,E), é apresentado a
seguir.
Modelo M:
sujeito a:
onde cij é o custo variável por unidade de fluxo no arco (i,j), xij é a
quantidade de fluxo no arco, fij é o custo fixo pelo uso do arco (i,j) para
transmissão do fluxo, yij é uma variável binária de decisão que assume o valor
0 se o arco (i,j) não está sendo usado e 1, caso contrário, d+(i) = {j|
(i,j)ÎE}, d-(i) = {j| (j,i) Î E}, di é a quantidade demandada pelo nó i, S é o
conjunto de nós de oferta, T é o conjunto de nós de Steiner, transbordo, e D é
o conjunto de nós de demanda.
A função objetivo (1) minimiza o custo total variável associado aos fluxos mais
o custo total fixo associado ao uso dos arcos. As restrições (2) garantem a
conservação dos fluxos nos diversos nós. Para os nós de oferta, a quantidade de
fluxo que chega menos a que sai deve ser igual ao somatório das demandas com o
sinal trocado. Essa parte da restrição é redundante, ou seja, a sua presença/
retirada não altera o conjunto de soluções viáveis do problema.
Conseqüentemente, também não altera a solução ótima. Nos nós de transbordo, a
quantidade de fluxo que chega deve ser igual à que sai. Finalmente, nos nós de
demanda, a quantidade de fluxo que chega menos a que sai deve ser igual à
demanda interna do nó di. As restrições (3) asseguram que não haja fluxo
através do arco (i,j) a menos que ele tenha sido selecionado na função
objetivo. É curioso notar que as restrições (3) são o que diferencia o problema
NCFCF, NP-árduo, do problema linear de fluxos, polinomial.
Com relação ao problema NCFCF aqui tratado, assumimos que o custo fixo fij seja
não negativo, pois caso contrário a variável yij poderia ser feita igual a 1 e
simplesmente eliminada do problema. A variável cij é irrestrita, mas para
garantir que a função objetivo seja limitada por baixo assumimos que não
existam circuitos com custo negativo.
2.2 Estado da Arte
Por se tratar de um problema de otimização NP-árduo, justificam-se tanto
abordagens exatas quanto aproximadas (heurísticas). De fato, vários trabalhos
têm sido publicados descrevendo algoritmos exatos e aproximados para o problema
NCFCF bem como para alguns casos particulares. Rothfarb et al. (1970),
modelando o problema de coleta de gás natural de estações em alto mar para
locais de armazenamento em terra, desenvolveram um algoritmo para resolver um
caso particular no qual era considerada uma estrutura de custos mais simples
sem custos variáveis nos arcos. Luna et al. (1987) estudaram um modelo um pouco
mais complexo e usado para modelar o problema de planejamento de redes locais
em telefonia tendo apresentado algoritmos heurísticos e algumas técnicas de
otimização local. Outro caso especial, sem nós de transbordo, foi tratado por
Magnanti et al. (1986) e por Hochbaum & Segev (1989) empregando algoritmos
do tipo separação e avaliação (do inglês branch-and-bound) associados à técnica
de decomposição de Benders e à relaxação Lagrangeana. Maiores detalhes sobre a
técnica de relaxação Lagrangeana a ser mencionada mais vezes neste artigo podem
ser encontrados no clássico trabalho de Fisher (1985).
Considerando o problema geral NCFCF, notamos contribuições tanto em algoritmos
exatos quanto aproximados. O leitor interessado poderá encontrar extenso
material no livro de Memhauser & Wolsey (1988) ou mais recentemente no
trabalho de Rardin & Wolsey (1993) que aborda modernas técnicas entre as
quais a teoria de inequações válidas (do inglês theory of valid inequalities).
Mateus et al. (1994) estudaram procedimentos heurísticos do tipo ADD e DROP,
conhecidos na área. Em Cruz et al. (1994), foi proposta uma heurística baseada
na relaxação Lagrangeana para solução do problema. Em outro artigo de Cruz et
al. (1998), um algoritmo exato do tipo separação e avaliação acoplado a testes
de redução foi desenvolvido com um desempenho prático satisfatório.
2.3 Algoritmos Considerados
Para questões de conveniência, todos os algoritmos aqui considerados são do
tipo separação e avaliação e estão baseados no algoritmo desenvolvido por Cruz
et al. (1998). Nesta classe de algoritmos, tenta-se resolver o modelo M gerando
limites superiores (i.e. soluções viáveis) e limites inferiores. Estes últimos
são usualmente determinados por alguma relaxação do problema original. Em Cruz
et al. (1998), é utilizada a relaxação Lagrangeana para esse fim (vide Fisher,
1985, para maiores detalhes). Se os limites superior e inferior são
coincidentes significa que o problema está resolvido sendo que a solução viável
é também uma solução ótima. Caso contrário, emprega-se algum critério para
escolher uma variável yij (e.g. o critério desenvolvido por Cruz et al., 1996)
que será então fixada nos dois valores possíveis 0 e 1 resultando em
subproblemas menores que terão seus limites inferior e superior novamente
computados. O algoritmo, ilustrado na Figura_3, fixará variáveis do problema
original tantas vezes quanto necessárias até resolvê-lo.
Conforme verificado empiricamente por Cruz et al. (1998), os algoritmos de
separação e avaliação têm um desempenho satisfatório e resolvem instâncias de
interesse prático de tamanho moderado em um tempo relativamente curto.
Entretanto, os limites inferiores gerados pela relaxação Lagrangeana obtida
diretamente do modelo M são fracos, i.e. são muito distantes do limite superior
correspondente. Pretende-se então apresentar resultados para algoritmos
derivados de uma modificação na formulação original do modelo M. O tipo de
modificação é utilizado corriqueiramente em problemas do gênero e consiste em
acrescentar ao modelo em estudo uma restrição redundante. Assim o modelo M
ganha a restrição:
onde Y é o conjunto de arcos presentes na solução, Y={(i,j) | yij=1}, |●| é a
cardinalidade do conjunto ● e Y e b é um limite inferior qualquer para esta
cardinalidade.
Somente para pequenos valores de b a restrição (6) é redundante. Isto pode ser
facilmente visto tomando-se como exemplo a solução apresentada na Figura_2 e
considerando-se que a mesma seja ótima. A utilização da formulação Mcom a
restrição adicional (6) e um b menor ou igual a 3 (o número de arcos presentes
na solução ótima) claramente não alteraria o ótimo. Ao contrário, se fosse
utilizado um b superior a 3, forçasse-ia a inclusão de um arco adicional. Note-
se que o problema com b superior a 7 não teria solução viável.
Um fato a considerar é que a relaxação Lagrangeana derivada do modelo M mais a
restrição (6) incluirá para sua resolução um procedimento de ordenação para o
qual a melhor implementação conhecida tem complexidade de tempo de execução O
(|E|log|E|) no caso médio (Ziviani, 1993). Uma questão importante é avaliar se
a restrição (6) traria ganho. Ou seja, deseja-se descobrir se essa restrição
adicional mesmo aumentando a complexidade computacional da nova relaxação seria
capaz de aumentar os limites inferiores gerados o suficiente para conseguir
melhorar globalmente o desempenho do algoritmo de separação e avaliação. Ainda
em outras palavras, é de interesse prático saber se este novo algoritmo
derivado da inclusão da restrição (6) resolve instâncias maiores do problema
NCFCF e mais rapidamente.
3.Planejamento e Execução dos Experimentos
Uma versão dos vários algoritmos foi codificada pelos autores na linguagem C++
e está disponível a pedido. Todos os testes aqui apresentados foram executados
no Laboratório de Pesquisa Operacional (LaPO) do Departamento de Ciência da
Computação da UFMG, utilizando-se uma estação de trabalho Sun Ultra 1 Modelo
140 com 128 MBytes de RAM e sistema operacional SunOS Release 5.5.1. Todos os
problemas de teste são derivados de grafos euclidianos gerados aleatoriamente
segundo procedimento desenvolvido por Aneja (1980) e já consagrado na área. De
acordo com tal procedimento, as posições dos nós, as extremidades dos arcos, os
seus pesos, o nó de oferta (consideramos apenas problemas com fonte única, por
questão de simplicidade) e os nós de demanda são escolhidos aleatoriamente
segundo a distribuição uniforme. Leitores interessados em maiores detalhes são
encorajados a consultar o trabalho de Aneja (1980).
Inicialmente, foram definidas 5 classes de problemas de interesse. A primeira
corresponde àqueles problemas com razão fij/cij=100. Esses são problemas
próximos ao problema de Steiner em grafos e muito difíceis de ser resolvidos
(NP-árduos). Para tais, esperam-se tempos de processamento maiores. Por outro
lado, a última classe corresponde àqueles problemas com razão fij/cij=0,01,
próximos ao problema linear de fluxos, computacionalmente fáceis (polinomiais).
Para estes, esperam-se tempos de processamento menores. A classe de problemas é
o correspondente ao fator A (Neter et al., 1990).
O algoritmo é o correspondente ao fator B, para o qual incluem-se medidas
repetidas. Os quatro algoritmos considerados para resolver cada um dos
problemas testes são descritos a seguir. O primeiro corresponde a resolver o
problema usando o modelo sem a restrição adicional significando que a
cardinalidade do conjunto Y foi deixada livre, i.e. não havia um limite para o
número mínimo de arcos presentes na solução do problema. O segundo algoritmo
também deixa a cardinalidade do conjunto livre, mas considera a restrição (6).
Esses dois casos foram considerados unicamente com o objetivo de verificar
empiricamente o impacto na dificuldade computacional da inclusão da restrição
(6) no modelo M e será mostrado que é significativo. Os demais casos fixam a
cardinalidade em dois valores. O terceiro considera uma cardinalidade mínima
óbvia e imediata pela consideração de que deve haver pelo menos um arco
entrando em cada um dos nós de demanda, o que significa que |Y.
Entretanto, conforme mostraremos na seção de análise dos resultados, esse
limite não é eficaz, pois não consegue reduzir substancialmente o número de
separações e avaliações nem o tempo de processamento. O quarto utiliza o limite
mais justo possível. Sobre a determinação desses limites justos, é importante
ressaltar que, infelizmente, no estágio atual da nossa pesquisa, somente
conseguimos calculá-los pela resolução completa do problema NCFCF através do
primeiro algoritmo.
Uma discussão mais aprofundada sobre o tamanho da amostra para cada combinação
classe x algoritmo foge ao escopo deste trabalho. Entretanto, é importante
ressaltar que este número não deve ser muito elevado, pois a consideração de
apenas 5 instâncias por combinação classe x algoritmo resultou na realização de
nada menos que 100 experimentos, mostrados na Tabela_1. Como procuram-se apenas
indícios da superioridade do algoritmo proposto, por comodidade optou-se por
considerar apenas estas 5 instâncias por combinação. Sendo observado o indício,
mais experimentos poderiam ser realizados, possivelmente reduzindo-se o número
de níveis nos fatores (e.g. apenas duas classes e dois algoritmos).
A Tabela_1 apresenta os resultados obtidos. Para cada uma das vinte e cinco
instâncias aleatórias testadas, mostramos a razão fij/cij e o número de arcos
presentes na solução ótima, |Y|*. Também apresentamos para cada um dos quatro
algoritmos testados o número total de separações e avaliações (coluna Nós) e o
tempo total (em segundos) gasto para processamento.
4. Análise dos Resultados
Na análise de variância, ambos os fatores A e B são de interesse, bem como a
possível interação entre eles. Por questão de simplicidade, consideramos apenas
o tempo de processamento como variável resposta de interesse, mas ressaltamos
que poderíamos estar interessados também em comparar os algoritmos por outro
critério de desempenho, tal como por exemplo quanto ao número total de
separações e avaliações. A transformação logarítmica é uma das mais utilizadas
em situações cuja resposta é o tempo até a ocorrência de um evento de interesse
(Lawless, 1982) para tornar simétrica a sua distribuição. Esta foi a
transformação usada na nossa análise. Em outras palavras, consideramos como
variável resposta de interesse o logaritmo dos tempos de UCP. Feito isto, foi
ajustado o seguinte modelo linear, adequado ao delineamento experimental
anteriormente descrito:
onde m...é o efeito geral da média, ri(j) são componentes de variância
independentes com distribuição N(0 ,sr2), ajé o efeito do fator A sujeito à
restrição åaj=0, bké o efeito do fator B sujeito à restrição åbk=0, (ab) jk é o
efeito da interação entre os dois fatores, sujeito à restrição å(ab) jk=0 tanto
em relação a j quanto em relação a k e e(ijk) é o erro aleatório com
distribuição N(0,s2) e independente de ri(j), para i=1,¼,n; j=1,¼,a; k=1,¼,b.
Todas as suposições associadas ao modelo (7) foram verificadas e confirmadas
(vide detalhes no Anexo). Na Tabela_2, apresentamos o resultado do ajuste do
modelo obtido utilizando o Minitab® (Minitab Inc., 2000). Pela coluna de p-
valores, notamos que tanto as classes de problemas quanto os algoritmos têm um
efeito significativo na variável resposta. Por outro lado, não há evidência de
que exista interação entre estes fatores. Podemos observar uma grande
variabilidade dentro das classes de problemas indicando ser alta a
heterogeneidade segundo este fator. Em outras palavras, a relação fij/cij tem
grande influência no tempo de resolução. Se esta relação é alta o problema
"tende" mais fortemente para um problema NP-árduo e exige mais
esforço computacional.
Prosseguindo, formamos intervalos de 90% de confiança para as médias,
apresentados na Figura_4. Os dados obtidos para o algoritmo 3 mostram fortes
evidências de que a inclusão da restrição (6) não melhora em nada o desempenho
médio do algoritmo de Cruz et al. (1998), a não ser que um limite muito forte
(correspondente ao algoritmo 4) fosse utilizado. Os dados também confirmam a
nossa conjectura de que problemas com uma razão fij/cij alta, mais
"próximos" do problema de Steiner em grafos, NP-árduo, são
significativamente mais difíceis de tratar não importando qual algoritmo esteja
sendo usado (pois a análise de variância não indicou interação significativa
entre os fatores classe de problema e algoritmo).
Outro aspecto notável à luz das amplitudes dos intervalos de confiança para as
diversas classes de problemas (Figura_4) é a natureza praticamente
determinística dos tempos de UCP para a resolução de problemas da classe 5,
"próximos" de um problema linear de fluxos. Por outro lado, é difícil
prever o tempo de UCP para resolução de um problema dentro da classe 1, que
"tende" a um problema de Steiner puro, NP-árduo.
5. Conclusões e Observações Finais
Apresentamos e discutimos a importância de um problema de otimização em redes,
o problema não capacitado de fluxos com custos fixos nos arcos (NCFCF).
Formulamos o problema NCFCF como um modelo de programação matemática inteira
mista para uma apresentação conveniente dos algoritmos que estamos comparando
estatisticamente. Este é um problema recorrente na área de desenvolvimento de
algoritmos. Utilizamos as técnicas de planejamento de experimentos, análise de
variância de um planejamento com medidas repetidas em um fator e construção de
intervalos de confiança para comparar os quatro algoritmos de interesse. Os
algoritmos propostos se basearam na conhecida idéia de utilização de restrições
redundantes e pelos experimentos realizados foi possível demonstrar que se pode
alcançar um desempenho superior com a estratégia. Entretanto, os resultados
também mostram que o desempenho global do algoritmo pode ser colocado em risco
se a restrição não produz a cada iteração melhorias suficientes para
compensarem o incremento que induz na complexidade computacional. O dilema
parece ser insolúvel para o caso geral e a experimentação com tratamento
estatístico dos dados parece ser uma ferramenta eficaz em casos particulares.
Neste sentido, a metodologia estatística aqui ilustrada pode ser útil nesta
tomada de decisão, pois por ser geral pode ser aplicada a qualquer outro
experimento que envolva comparações múltiplas de natureza semelhante.
Trabalhos futuros poderiam envolver a comparação dos algoritmos descritos
segundo outros critérios de desempenho (e.g. o espaço de memória máximo
exigido). Poderiam incluir a investigação de outros tipos de algoritmos. Em
particular, algoritmos paralelos apresentam peculiaridades para a tomada de
suas medidas de desempenho (Cruz & Mateus, 2001) pela dificuldade de
isolamento das máquinas na realização dos experimentos. Mais este fator (carga
do sistema) teria que ser levando em consideração modificando um pouco o
delineamento experimental. Adicionalmente, outros tipos de planejamentos
poderiam ser considerados para verificação da sua adequação ao problema de
comparação múltipla de algoritmos (e.g. o delineamento em parcelas
subdivididas). Em Neter et al. (1990), o tema é apresentado em abrangência
sendo portanto uma fonte de consulta recomendável para outras situações
envolvendo outros tipos de planejamentos.
