The usual approach to solving a piecewise linear network flow problem is to transform it into an equivalent linear one. In this transformation, a piecewise network with n nodes and m arcs, each with intervals to each linear piece of the cost function associated to arc j, has an equivalent linear one with n nodes and = arcs. Interior point methods have been proved successful in the solution of linear network flow problems. We show that is advantageous to construct a customized interior point method to solve piecewise linear network problems directly, instead of applying its generic version to the equivalent linear problem. Two algorithms were implemented and tested: one using predictor-corrector and the other without the corrector step. Comparison between alternative strategies (initialization and stopping criteria) is done by means of several computational tests.
A abordagem usual de solução de um problema de fluxo em rede linear por partes é a sua transformação em um problema equivalente de fluxo em rede linear. Nesta transformação, uma rede linear por partes com n nós e m arcos, cada um com intervalos para cada parte linear da função de custo associada ao arco j, tem uma rede linear associada com n nós e = arcos. Métodos de pontos interiores têm se apresentado muito bem na resolução de problemas de fluxo em redes lineares. Nós mostramos que é vantajoso construir um método de pontos interiores especializado para resolver problemas em redes lineares por partes diretamente, ao invés de aplicar uma versão genérica no problema linear equivalente. Dois algoritmos foram implementados e testados: um utilizando o passo preditor-corretor e o outro sem utilizar o passo corretor. Comparações entre diferentes estratégias alternativas (inicialização e critério de parada) são realizadas para efeito de testes computacionais
