Bayesian networks are important Machine Learning models with many practical applications in, e.g., biomedicine and bioinformatics. The problem of Bayesian networks learning is$\mathcal {NP}$-hard and computationally challenging. In this article, we propose practical parallel exact algorithms to learn Bayesian networks from data. Our approach uses shared-memory task parallelism to realize exploration of dynamic programming lattices emerging in Bayesian networks structure learning, and introduces several optimization techniques to constraint and partition the underlying search space. Through extensive experimental testing we show that the resulting method is highly scalable, and it can be used to efficiently learn large globally optimal networks.

We propose SCoOL, a programming model and its corresponding parallel runtime systems for implementing optimization problem solvers. In SCoOL, users specify what task is performed for a point in a given search space, and what global information should be maintained during the search. The resulting optimization program is then efficiently executed in a BSP-style on a shared or distributed memory computers by a parallel runtime provided with the model. In the paper, we show details of our scalable runtime for distributed memory clusters, including algorithms for work stealing and tasks rebalancing. To benchmark the platform, we implement solutions to several optimization problems and provide performance analysis for Quadratic Assignment Problem, Parent Set Assignment, and Bayesian Networks Structure Learning. Our solvers show strong scaling on a cluster with 1,280 cores, significantly outperforming the current state-of-the-art solvers in Bayesian networks learning.