Machine-Learning–Based Column Selection for Column Generation

Mouad Morabit (), Guy Desaulniers () and Andrea Lodi ()
Additional contact information
Mouad Morabit: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Québec H3C 3A7, Canada; Research Group in Decision Analysis (GERAD), Montréal, Québec H3T 2A7, Canada; Canada Excellence Research Chair in Data Science for Real-Time Decision-Making, Polytechnique Montréal, Quebec H3C 3A7, Canada
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Québec H3C 3A7, Canada; Research Group in Decision Analysis (GERAD), Montréal, Québec H3T 2A7, Canada
Andrea Lodi: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Québec H3C 3A7, Canada; Research Group in Decision Analysis (GERAD), Montréal, Québec H3T 2A7, Canada; Canada Excellence Research Chair in Data Science for Real-Time Decision-Making, Polytechnique Montréal, Quebec H3C 3A7, Canada

Transportation Science, 2021, vol. 55, issue 4, 815-831

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 problem with time windows. The ML model was 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 (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1045 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:4:p:815-831

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().