This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural equation model. We consider an $\ell_0$-penalized maximum likelihood estimator for this problem, which is known to have favorable statistical properties but is computationally challenging to solve, especially for medium-sized Bayesian networks. We propose a new coordinate descent algorithm to approximate this estimator and prove several remarkable properties of our procedure: The algorithm converges to a coordinate-wise minimum, and despite the non-convexity of the loss function, as the sample size tends to infinity, the objective value of the coordinate descent solution converges to the optimal objective value of the $\ell_0$-penalized maximum likelihood estimator. To the best of our knowledge, our proposal is the first coordinate descent procedure endowed with optimality guarantees in the context of learning Bayesian networks. Numerical experiments on synthetic and real data demonstrate that our coordinate descent method can obtain near-optimal solutions while being scalable.

Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as a mixed-integer program with an objective function composed of a convex quadratic loss function and a regularization penalty subject to linear constraints. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. However, the state-of-the-art optimization solvers are not able to obtain provably optimal solutions to the existing mathematical formulations for medium-size problems within reasonable computational times. To address this difficulty, we tackle the problem from both computational and statistical perspectives. On the one hand, we propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution to the mixed-integer program, and establish the consistency of this approximate solution. On the other hand, we improve the existing formulations by replacing the linear “big-$M$" constraints that represent the relationship between the continuous and binary indicator variables with second-order conic constraints. Our numerical results demonstrate the effectiveness of the proposed approaches.

Flow cover inequalities are among the most effective valid inequalities for capacitated fixed-charge network flow problems. These valid inequalities are based on implications for the flow quantity on the cut arcs of a two-partitioning of the network, depending on whether some of the cut arcs are open or closed. As the implications are only on the cut arcs, flow cover inequalities can be obtained by collapsing a subset of nodes into a single node. In this article, we derive new valid inequalities for the capacitated fixed-charge network flow problem by exploiting additional information from the network. In particular, the new inequalities are based on a three partitioning of the nodes. The new three-partition flow cover inequalities include the flow cover inequalities as a special case. We discuss the constant capacity case and give a polynomial separation algorithm for the inequalities. Finally, we report computational results with the new inequalities for networks with different characteristics. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 299–315 2016

We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and set packing problems with random coefficients. We propose a problem formulation in its original space based on the so-called probabilistic covers. We focus our solution approaches on the special case in which the uncertainty is represented by a finite number of scenarios. In this case, the problem can be formulated as an integer program by introducing a binary decision variable to represent feasibility of each scenario. We derive a computationally efficient coefficient strengthening procedure for this formulation, and demonstrate how the scenario variables can be efficiently projected out of the linear programming relaxation. We also study how methods for lifting deterministic cover inequalities can be leveraged to perform approximate lifting of probabilistic cover inequalities. We conduct an extensive computational study to illustrate the potential benefits of our proposed techniques on various problem classes.