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.

Partindo de minha implementação revisada, desenvolvi uma implementação para uma versão alternativa do método dos caminhos de aumento, conhecida como algoritmo dos fluxos bloqueadores de aumento. Enquanto isso, o Marcelo modificou sua versão da implementação e desenvolveu implementações para os algoritmos dos caminhos de maior aumento e capacity scaling.

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. Eu fiquei encarregada de estudar e implementar a versão do método conhecida como fila de vértices ativos e o Marcelo se encarregou dos algoritmos de vértices ativos 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 de complexidade ligeiramente diferentes e mais simples.

Com as implementações do método do pré-fluxo já encaminhadas, começamos a estudar o problema do fluxo 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. Eu me encarreguei do método do cancelamento de circuitos e do algoritmo cost scaling enquanto o Marcelo cuidou 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. Além disso, elas foram desenvolvidas diretamente em CWEB.

Paralelamente às implementações dos algoritmos para o problema do fluxo de custo mínimo, estudamos o algoritmo simplex para redes. Tivemos algumas discussões relacionadas ao seu funcionamento e procuramos compreender como tal algoritmo está relacionado ao método simplex para a resolução de problemas de programação linear. Estudamos, por exemplo, como os custos reduzidos associados aos vértices de uma rede estão relacionados às variáveis duais da formulação do problema do fluxo de custo mínimo como um programa linear. Um aspecto interessante desse estudo foi a oportunidade que tivemos para fazer uma revisão mais aprofundada da teoria envolvida no método simplex.

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.