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 on the basis of the linear programming solvers of CPLEX, Gurobi and SoPlex. The column generation approach turns out to be superior to the dual simplex algorithm for instances with a large number of sources/demands and large capacities. Using interior point (barrier) methods is not competitive. Moreover, stabilization of the column generation does not have a significant positive effect overall, but a path initialization heuristic does.