Machine-learning-based column selection for column generation
Mouad Morabit, Guy Desaulniers, Andrea Lodi
Abstract
Column generation (CG) is widely used for solving large-scale optimization problems. This article presents a new approach based on a machine learning (ML) technique to accelerate CG. This approach, called column selection, applies a learned model to select a subset of the variables (columns) generated at each iteration of CG. The goal is to reduce the computing time spent reoptimizing the restricted master problem at each iteration by selecting the most promising columns. The effectiveness of the approach is demonstrated on two problems: the vehicle and crew scheduling problem and the vehicle routing problemwith timewindows. TheMLmodelwas able to generalize to instances of different sizes, yielding a gain in computing time of up to 30%.