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.