Column Generation in the Primal-Dual Linear Programming Algorithm

We combine the primal-dual linear programming algorithm with Dinkelbach's Newton-type fractional programming method to solve large scale linear programming problems normally solved by column generation. We test this primal-dual column generation method on one-dimensional bin packing problems and on vehicle routing problems with time windows. The primal-dual column generation algorithm solved the vehicle routing problems faster than classical column generation. However, classical column generation outperformed the primal-dual algorithm on the bin packing problems.