We introduce a structured learning approach to approximate a difficult path problem on an acyclic digraph by the usual shortest path problem. The approach takes in input a database of instances and solutions of the difficult path problem of interest, and returns a mapping that transforms any instance of the difficult path problem into an instance of the usual shortest path problem that approximates well the initial instance. To that purpose, we introduce a maximum likelihood technique to train a structured prediction function which uses a shortest path problem as prediction problem.

This provides a generic technique to derive an efficient heuristic from a black-box solver that can handle only instances of moderate size of a path problem of interest: We use the black-box solver to generate a database of instance and solutions and train our structured learning method. (Large) new instances can then be handled by solving their approximation by a usual shortest path problem using standard algorithms.

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 a stochastic vehicle scheduling problem.