In numerous systems, especially in communication networks, it is a key functionality to find optimal paths in massive graphs. In order to understand the system, we need to know the specific path metric under which the optimal paths are chosen. In many cases, however, no explicit knowledge of the metric is available, due to the multitude of factors that implicitly influence the selections. We can only observe the eventual path choices that are made by an unknown mechanism between various end nodes, but we are not familiar with the underlying metric. Our goal is to learn the unknown metric, as accurately as possible, purely from the observed path choices. We present an inverse optimization based mathematical model, along with a solution algorithm, to handle this problem. Our main result is that the unknown path metric can be optimally learned from the observed path choices by a polynomial time algorithm, if we assume that the metric is additive, but otherwise arbitrary. Thus, the powerful tool of inverse optimization offers an efficient learning method for the considered problem.
In this paper we investigate how three widely used decomposition techniques can be accelerated when intertwined with a matheuristic. More precisely, we consider the Benders decomposition, Lagrangean relaxation, and Dantzig-Wolfe reformulation techniques and hybridize them with the corridor method. We exemplify the proposed approaches on the capacitated lot sizing problem with setups. Our computational analysis on a set of benchmark instances shows that all the decomposition methods benefit from the hybridization with the corridor method, and that this is especially evident in the case of the Benders decomposition algorithm.