# Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

arXiv: https://arxiv.org/abs/1904.10574 · HTML: https://mlsanity.com/paper/1904.10574/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2019.

## Built on by (most cited first, 20 of 20)

- [Integer Programming for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2102.03129/) (2021)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [Multi-task Learning of Order-Consistent Causal Graphs](https://mlsanity.com/paper/2111.02545/) (2021)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [ProDAG: Projected Variational Inference for Directed Acyclic Graphs](https://mlsanity.com/paper/2405.15167/) (2024)
- [Differentiable Invariant Causal Discovery](https://mlsanity.com/paper/2205.15638/) (2022)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Learning Directed Acyclic Graphs from Partial Orderings](https://mlsanity.com/paper/2403.16031/) (2024)
- [Definite Non-Ancestral Relations and Structure Learning](https://mlsanity.com/paper/2105.10350/) (2021)
- [Causal Graph Discovery from Self and Mutually Exciting Time Series](https://mlsanity.com/paper/2301.11197/) (2023)
- [An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models](https://mlsanity.com/paper/2408.11977/) (2024)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Causal Graph Discovery from Self and Mutually Exciting Time Series](https://mlsanity.com/paper/2106.02600/) (2021)
- [Causal Structural Learning from Time Series: A Convex Optimization Approach](https://mlsanity.com/paper/2301.11336/) (2023)
- [Learning Dynamic Bayesian Networks from Data: Foundations, First Principles and Numerical Comparisons](https://mlsanity.com/paper/2406.17585/) (2024)
- [Empirical Bayes for Dynamic Bayesian Networks Using Generalized Variational Inference](https://mlsanity.com/paper/2406.17831/) (2024)
- [ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulations](https://mlsanity.com/paper/2410.16100/) (2024)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

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 ℓ0 and ℓ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 ℓ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.