Atividades realizadas
Inicialmente, estudamos alguns tópicos de otimização combinatória
através dos livros de Cook et al. [5], Schrijver [18] e Cormen et al. [6] para nos familiarizar um pouco mais com
a teoria envolvida nos problemas. Em particular, fizemos uma pequena
revisão de programação linear, estudamos o problema dos caminhos
mínimos sob o ponto de vista da combinatória poliédrica e discutimos
algumas questões sobre unimodularidade total. Partimos então
para o problema do fluxo máximo e a partir desse ponto a base
teórica de nossos estudos foi quase puramente o livro de Ahuja, Magnanti e Orlin [1], como estava previsto no planejamento inicial.
Antes de nos dedicarmos a fundo ao estudo teórico do problema,
trabalhamos em cima de uma implementação em C para um
algoritmo que o resolve, conhecido como método
dos caminhos de aumento, que fizemos para a disciplina
MAC0328 - Algoritmos em Grafos. A implementação utilizava a
plataforma SGB e aplicava ao método uma especialização conhecida como algoritmo dos caminhos de aumento de comprimento
mínimo.
A Juliana se baseou na implementação original para desenvolver uma
versão alternativa do algoritmo, conhecida como algoritmo dos
fluxos bloqueadores de aumento. Eu trabalhei em cima do código original,
modificando-o para que passasse a executar os algoritmos dos caminhos de maior
aumento e capacity scaling. Durante o desenvolvimento do
primeiro, houve a necessidade da implementação de uma fila de
prioridade. A primeira versão funcional utilizava uma fila trivial e
ineficiente. Para a segunda eu estudei e utilizei uma estrutura de dados conhecida como
leftist heap, que acabou se mostrando inadequada para o
problema. A terceira e atual versão utiliza um heap, cuja
implementação foi baseada no livro Introduction to
Algorithms [6] e cujo desempenho é satisfatório.
Realizamos pequenos testes experimentais com as implementações que
fizemos para verificar e comparar seus desempenhos. Os testes iniciais
foram feitos sobre instâncias básicas do problema. Para a maioria dos
experimentos, porém, utilizamos um gerador de instâncias desenvolvido
por Cherkassky e Goldberg [20], capaz de gerar entradas
grandes e reconhecidamente difíceis para os algoritmos que foram implementados.
Após a execução e análise dos testes mencionados, começamos a estudar
mais a fundo os conceitos abordados em nosso livro-texto e a discutir
algumas dúvidas teóricas entre nós e com o orientador. As principais
discussões foram em torno da análise da complexidade dos algoritmos e
da modelagem do problema sob o contexto de programação linear e dualidade. Estudamos a teoria
envolvida nos conceitos básicos do problema do fluxo máximo,
particularmente o teorema do fluxo
máximo e corte mínimo, e na análise dos algoritmos de caminhos
de aumento. Também discutimos alguns aspectos referentes à busca
de fluxos em grafos acíclicos,
como o funcionamento e análise do algoritmo de Karzanov [24].
A partir mais ou menos desse ponto, começamos a desenvolver o nosso
texto teórico. Até então, havíamos escrito apenas alguns rascunhos
iniciais com o objetivo de decidir qual seria a melhor notação e em
que pontos deveríamos divergir de nossas referências. O
desenvolvimento da versão definitiva se mostrou bem difícil e durante
um longo período a iniciação resumiu-se ao estudo das referências e ao
processo de incrementar e corrigir nosso texto teórico, sem muita
ênfase na parte de implementação.
Após formalizar os conceitos do método dos caminhos de aumento,
iniciamos o estudo de um outro algoritmo para o problema do fluxo
máximo, conhecido como método do
pré-fluxo. A
Juliana ficou encarregada de estudar e implementar a versão do método
conhecida como algoritmo da fila de vértices ativos
e eu me encarreguei dos algoritmos de vértices de maior rótulo e excess scaling. Algumas novas discussões teóricas
interessantes foram levantadas durante esse período. Questionamos a
razão do uso de algumas notações em nossas referências e conseguimos desenvolver
algumas análises diferentes e mais elegantes.
Os algoritmos de pré-fluxo que implementei foram codificados
diretamente na linguagem CWEB e, nesse período, aproveitei
para converter as implementações do método dos caminhos de aumento
também para CWEB. Não houveram problemas com estruturas de
dados e cabe mencionar que as estruturas recomendadas pelas nossas
referências funcionaram perfeitamente. Um pouco de tempo foi perdido
para corrigir um erro presente em minha implementação do algoritmo
excess scaling: descobri posteriormente que o heap utilizado no algoritmo dos caminhos de maior
aumento, e que copiei e colei para o excess scaling, estava incorreto.
O erro não havia sido detectado antes porque ele não tornava o
algoritmo dos caminhos de maior aumento incorreto, apenas menos
eficiente.
Com as implementações do método do
pré-fluxo já encaminhadas, começamos a estudar o problema do fluxo viável de custo
mínimo. Discutimos um pouco a respeito da equivalência das
diferentes condições de
otimalidade existentes e de como elas estão relacionadas com a
modelagem do problema em programação linear. Houve uma breve discussão
sobre o algoritmo out-of-kilter e sobre suas diferenças em relação a
outros algoritmos.
Devido à limitação de tempo, não houve oportunidade de tantas
discussões como no caso do problema do fluxo máximo. Logo partimos, de
maneira um pouco apressada, para a formalização teórica dos conceitos
e para as implementações. A Juliana encarregou-se do método do cancelamento de circuitos
e do algoritmo cost scaling
enquanto eu cuidei do método dos
caminhos de viabilidade e do algoritmo path scaling. Um aspecto interessante dessas implementações
foi o fato de elas envolverem a resolução de um problema de fluxo
máximo como pré-processamento. Pudemos reutilizar as implementações
anteriores para facilitar.
Como o simplex para redes é um algoritmo que resolve qualquer problema
sobre fluxos em redes que possa ser modelado como um problema de fluxo
de custo mínimo, procuramos também relacionar seu funcionamento ao
funcionamento dos algoritmos polinomiais que estudamos para os
problemas específicos.
Com as implementações dos algoritmos para o problema do fluxo máximo
e para o problema do fluxo de custo mínimo feitas, pudemos realizar os
testes experimentais. Além do gerador de instâncias de Goldberg, utilizamos
um conjunto de instâncias disponível na página de Schmidt [25]. A partir
daí, nos dedicamos a melhorar e refinar todos os documentos
e a organizar o sítio do projeto.
|