Machine-Learning-Based Column Selection for Column Generation

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%.

Automated summary

Column generation (CG) is widely used for solving large-scale optimization problems, and this article presents a new approach using machine learning (ML) to accelerate CG by selecting promising columns to reduce computing time by up to 30% for problems such as vehicle and crew scheduling and vehicle routing with timewindows.