Learning to Approximate Industrial Problems by Operations Research Classic Problems

• 成果类型: Article
• 署名作者: Parmentier, Axel
• 署名单位: Institut Polytechnique de Paris; Ecole des Ponts ParisTech
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2094
• 发表日期: 2022
• 页码: 606-623
• 关键词: machine learning for operations research; structured learning; path problem; Column Generation; matheuristic; stochastic vehicle scheduling problem

摘要

Practitioners of operations research often consider difficult variants of well-known optimization problems and struggle to find a good algorithm for their variants although decades of research have produced highly efficient algorithms for the well-known problems. We introduce a machine learning for operations research paradigm to build efficient heuristics for such variants: use a machine learning predictor to turn an instance of the variant into an instance of the well-known problem, then solve the instance of the well-known problem, and finally retrieve a solution of the variant from the solution of the well-known problem. This paradigm requires learning the predictor that transforms an instance of the variant into an instance of the well-known problem. We introduce a structured learning methodology to learn that predictor. We illustrate our paradigm and learning methodology on path problems. We, therefore, introduce a maximum likelihood approach to approximate an arbitrary path problem on an acyclic digraph by a usual shortest path problem. Because path problems play an important role as pricing subproblems of column-generation approaches, we introduce matheuristics that leverage our approximations in that context. Numerical experiments show their efficiency on two stochastic vehicle scheduling problems.