Decomposition methods for network multiflows problems

Este trabalho apresenta um estudo sobre problemas de multifluxo em redes, juntamente com três abordagens de solução: o Particionamento Primal, a Decomposição Recurso-Diretor e a Decomposição Dantzig-Wolfe. O produto num problema de multifluxo pode ser definido de três maneiras. Cada uma dessas definições para produto produz uma formulação distinta para o problema de multifluxo: o Problema Produto Específico (PPE), o Problema do Destino Específico (PDE) e o Problema Origem e Destino Específico (POD). Neste trabalho foi feita uma investigação do impacto das três formulações sobre a decomposição de Dantzig-Wolfe.This work presents a study on multicommodity network flows problem and three solution approaches: Primal Partitioning, Resourse-directive Decomposition, Dantzig-Wolfe decomposition. A commodity in a network flow problem can be formulated by three ways leading to three different mathematical models: product specific problem (PSP), destination specific problem (DSP) and origin-destination problem (ODP). We also prese,nt an investigation of impact of problem formulation on Dantzig-Wolfe decomposition