Improved Column Generation for Highly Degenerate Master Problems

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more