The sharpest column: stabilizing column generation for the bin packing problem via a lexicographic pricer
Abstract: 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.
Keywords: bin packing; column generation; stabilization techniques.
Category 1: Combinatorial Optimization
Category 2: Integer Programming
Entry Submitted: 07/11/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|