The sharpest column: stabilizing column generation for the bin packing problem via a lexicographic pricer

Stefano Coniglio(s.conigliosoton.ac.uk)
Fabio D’Andreagiovanni(d.andreagiovannihds.utc.fr)
Fabio Furini(fabio.furinidauphine.fr)

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

Citation:

Download: [PDF]

Entry Submitted: 07/11/2018
Entry Accepted: 07/11/2018
Entry Last Modified: 07/11/2018

Modify/Update this entry