Column generation for solving linear programs with a huge number of variables alternately solves a (restricted) master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy, exposing what is known as tailing-off effect. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose an improved column generation (ICG) method that takes advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of non-degenerate basic variables in the current master problem solution. The advantage of this row-reduction is a smaller basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem that needs to generate variables compatible with the row-reduction, if possible. Otherwise, incompatible variables may need to be added, and the row-reduction is dynamically updated. We show that, in either case, a strict improvement in the objective function value occurs. We further discuss extensions and some implementation issues.

Two special cases of ICG are the improved primal simplex method and the dynamic constraints aggregation. On highly degenerate linear programs, recent computational experiments with these algorithms show that the row-reduction of a problem might have a larger impact on the solution time than the column-reduction of standard column generation.