In spite of being an extremely successful method to tackle mathematical programs involving a very large number of variables, Column Generation (CG) is known to suffer from stabilization issues which can slow down its convergence significantly. In this article, we propose a new parameter-free stabilization technique for CG based on solving a lexicographic pricing problem. Using the bin packing problem as case study, we show that, computationally, the new stabilization technique allows for a substantial reduction in the number of columns that are generated to solve the problem. While we present the approach for the bin packing problem, our methodology is general and can be applied to other classes of problems solved via CG.
View The sharpest column: stabilizing column generation for the bin packing problem via a lexicographic pricer