Experimentos com programas lineares por partes em redes

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 $k$ intervals (corresponding to the linear pieces of the arc cost function), has an equivalent linear one with $n$ nodes and $m k$ arcs. Interior point methods have been proved successful in the solution of linear network flow problems. We show that it is advantadgeous to construct a customized interior point method to solve piecewise network problems directly, instead of applying its generic version to the equivalent linear problem. Two algorithms were implemented and tested: one using preditor-corrector and the other without the corrector step. Comparison between alternative strategies (initialization, stopping criteria) are done by means of several computacional tests.