Integer Programming for Learning Directed Acyclic Graphs from Continuous
  Data
  Learning directed acyclic graphs (DAGs) from data is a challenging task both
in theory and in practice, because the number of possible DAGs scales
superexponentially with the number of nodes. In this paper, we study the
problem of learning an optimal DAG from continuous observational data. We cast
this problem in the form of a mathematical programming model which can
naturally incorporate a super-structure in order to reduce the set of possible
candidate DAGs. We use the penalized negative log-likelihood score function
with both $\ell_0$ and $\ell_1$ regularizations and propose a new mixed-integer
quadratic optimization (MIQO) model, referred to as a layered network (LN)
formulation. The LN formulation is a compact model, which enjoys as tight an
optimal continuous relaxation value as the stronger but larger formulations
under a mild condition. Computational results indicate that the proposed
formulation outperforms existing mathematical formulations and scales better
than available algorithms that can solve the same problem with only $\ell_1$
regularization. In particular, the LN formulation clearly outperforms existing
methods in terms of computational time needed to find an optimal DAG in the
presence of a sparse super-structure.
