A hybrid algorithm for solving network flow problems with side constraints

We consider network flow problems with few additional linear side constraints. Three approaches for solving such problems are presented. The first method is a specialized Simplex Algorithm with primal partitioning of the basis. Secondly, Lagrangean relaxation is used, solving the dual problem by subgradient optimization. Finally, good starting solutions are generated by relaxing the side constraints, solving the resulting pure network problem, and using the solution of the pure network problem as an advanced start for a general LP-optimizer. Numerical tests show that a hybrid combination of Lagrangean relaxation and subsequent optimization by primal partitioning is most efficient.