Column Generation for Generalized Min-Cost Flows with Losses
\(\)
The generalized flow problem deals with flows through a network with losses or gains along the arcs. Motivated by energy networks, this paper concentrates on the case with losses along cycles. Such networks can become extremely large, mostly because they are considered over large time horizons. We therefore develop a column generation approach for a path-based formulation. The pricing problems amount to finding shortest paths with loss factors, which we show to be solvable in \(O(n m)\) by dynamic programming, where \(n\) is the number of nodes and \(m\) the number of arcs. We then perform a comprehensive computational comparison of the column generation approach on the path-based formulation and the dual simplex algorithm on the arc-based model. Solving the path formulation turns out to be superior to the arc formulation for instances with a large number of sources/demands and large capacities or if memory is critical. Using interior point (barrier) methods is not competitive. Moreover, the implemented stabilization scheme does not have a significant positive effect overall, but a path initialization heuristic does.