Network Models with Convex Cost Structure like Bundle Methods

Abstract

For three rather diverse applications (truck scheduling for inter warehouse logistics, university-course timetabling, operational train timetabling) that contain integer multi-commodity flow as a major modeling element we present a computational comparison between a bundle and a full linear programming (LP) approach for solving the basic relaxations. In all three cases computing the optimal solutions with LP standard solvers is computationally very time consuming if not impractical due to high memory consumption while bundle methods produce solutions of sufficient but low accuracy in acceptable time. 
The rounding heuristics generate comparable results for the exact and the approximate solutions, so this entails no loss in quality of the final solution. Furthermore,  bundle methods facilitate the use of nonlinear convex cost functions. In practice this not only improves the quality of the relaxation but even seems to speed up convergence of the method.