Learning to Approximate Industrial Problems by Operations Research Classic Problems

Axel Parmentier ()
Additional contact information
Axel Parmentier: Cermics, Ecole des Ponts, 77420 Champs-sur-Marne, France

Operations Research, 2022, vol. 70, issue 1, 606-623

Abstract: 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.

Keywords: Optimization; machine learning for operations research; structured learning; path problem; column generation; matheuristic; stochastic vehicle scheduling problem (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2094 (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:oropre:v:70:y:2022:i:1:p:606-623

Access Statistics for this article

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