Capacitated multicommodity network flow problems with piecewise linear concave costs

Lagrangian techniques have been commonly used to solve the capacitated multi-commodity network flow problem with piecewise linear concave costs. In this paper, we show that the resulting lower bounds are no better than those obtained by the linear programming relaxation and focus on developing algorithms based on the latter. For that purpose, we characterize structural properties of the optimal solution of the linear programming relaxation and propose a heuristic solution approach that uses these properties to transform the fractional solution into an integer one. Our computational experiments show the effectiveness of the algorithm.