|
Parte Técnica
Parte Subjetiva |
Objetivos e metodologia Neste projeto de iniciação científica, nós estudamos algumas das ferramentas mais fundamentais em otimização combinatória através do estudo, implementação e análise experimental de algoritmos para problemas clássicos envolvendo fluxos em redes. Um dos objetivos foi a nossa preparação para uma pós-graduação na área. A principal fonte dos algoritmos incluídos no estudo, e também a principal base teórica, foi o livro Network Flows de Ahuja, Magnanti e Orlin [1]. Também utilizamos bastante a teoria do livro Combinatorial Optimization de Cook, Cunningham, Pulleyblank e Schrijver [5]. Como corolário de nosso estudo, produzimos um texto científico contendo a descrição de toda a teoria envolvida nos problemas e em cada um dos algoritmos estudados. A linguagem algoritmica utilizada segue os padrões das notas de aula de Paulo Feofiloff [10], que nos permitiram destacar de maneira simples a razão pela qual os algoritmos funcionam. Cabe ressaltar que o texto produzido não é uma mera reprodução ou resumo do conteúdo das nossas referências, mas um texto independente e auto-contido que freqüentemente diverge delas em termos de notação, rigidez e até mesmo em aspectos como demonstrações de teoremas. Outro produto da nossa iniciação foi uma biblioteca de implementações dos algoritmos estudados, que nos permitiu realizar um estudo comparativo de desempenho experimental. Um documento contendo todos os detalhes desse estudo comparativo também foi produzido. Uma de nossas intenções com o projeto era disponibilizar todas as implementações em um sítio da Internet nos moldes da Network Optimization Library de Andrew Goldberg [20]. Por isso, para que as implementações pudessem ser facilmente compreendidas e utilizadas por outras pessoas, elas foram feitas na linguagem CWEB [21] de programação literária [22] e utilizaram a plataforma combinatória SGB [23], desenvolvida por Knuth. |
