.png){kind=icon}
.png){kind=icon}
Return
Machine-Learning-Based Column Selection for Column Generation
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.2021.1045.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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%.
Keywords:
column generation
machine learning
column selection