  We study the problem of learning directed acyclic graphs from continuous
observational data, generated according to a linear Gaussian structural
equation model. State-of-the-art structure learning methods for this setting
have at least one of the following shortcomings: i) they cannot provide
optimality guarantees and can suffer from learning sub-optimal models; ii) they
rely on the stringent assumption that the noise is homoscedastic, and hence the
underlying model is fully identifiable. We overcome these shortcomings and
develop a computationally efficient mixed-integer programming framework for
learning medium-sized problems that accounts for arbitrary heteroscedastic
noise. We present an early stopping criterion under which we can terminate the
branch-and-bound procedure to achieve an asymptotically optimal solution and
establish the consistency of this approximate solution. In addition, we show
via numerical experiments that our method outperforms state-of-the-art
algorithms and is robust to noise heteroscedasticity, whereas the performance
of some competing methods deteriorates under strong violations of the
identifiability assumption. The software implementation of our method is
available as the Python package \emph{micodag}.
