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 while 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 of well-known problems. If we call the difficult problem of interest the hard problem, and the well known one the easy problem, we can describe our paradigm as follows. First, use a machine learning predictor to turn an instance of the hard problem into an instance of the easy one, then solve the instance of the easy problem, and finally retrieve a solution of the hard problem from the solution of the easy one. Using this paradigm requires to learn the predictor that transforms an instance of the hard problem into an instance of the easy one. We show that the problem of learning such a predictor from a training set containing instances of the hard problem and their optimal solutions can be reformulated as a structured learning problem, whose structured prediction problem is the easy problem. This provides algorithms to learn our predictor if the easy problem has been considered as a structured prediction problem in the literature, and a methodology to build the learning algorithm if not. We illustrate our paradigm and learning methodology on path problems. To that purpose, we introduce a maximum likelihood technique to train a structured prediction model which uses a shortest path problem as prediction problem. Using our paradigm, this enables to approximate an arbitrary path problem on an acyclic digraph (the hard problem) by a usual shortest path problem (the easy problem). Since path problems play an important role as pricing subproblems of column generation approaches, we also introduce matheuristics that leverage our approximations in that context. Numerical experiments show their efficiency on two stochastic vehicle scheduling problems