Problema do fluxo de custo mínimo

Suponha que uma empresa administra um conjunto de estabelecimentos formado por fábricas e depósitos de um determinado produto. Cada fábrica produz uma certa quantidade do produto e cada depósito deve armazenar uma certa quantidade. Os estabelecimentos são interconectados por uma rede de vias de transporte, como por exemplo estradas, sobre a qual são definidos custos de transporte e limites para a quantidade transportada. O desejo da empresa é estabelecer uma distribuição do produto sobre essa rede de forma a satisfazer as ofertas e demandas dos estabelecimentos, respeitar os limites das estradas e minimizar o custo total de transporte. Este é um exemplo de instância do problema conhecido como problema do fluxo de custo mínimo.

Uma das primeiras abordagens do problema, o método do cancelamento de circuitos, foi proposta por Goldberg e Tarjan [14] e utilizava a idéia de reduzir o custo do fluxo através de circuitos negativos. Edmonds e Karp [9] propuseram o método dos caminhos de viabilidade e Orlin [17] idealizou uma maneira de implementar esse método de forma a consumir tempo polinomial, o que resultou no algoritmo path scaling. Goldberg e Tarjan [15] também propuseram um algoritmo extremamente eficiente para o problema, conhecido como algoritmo cost scaling, que utiliza aproximações sucessivas.