Learning to Approximate Industrial Problems by Operations Research Classic Problems

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.