Skip to main content

Research Repository

Advanced Search

Integer linear programming for the Bayesian network structure learning problem.

Bartlett, Mark; Cussens, James


James Cussens


Bayesian networks are a commonly used method of representing conditional probability relationships between a set of variables in the form of a directed acyclic graph (DAG). Determination of the DAG which best explains observed data is an NP-hard problem. This problem can be stated as a constrained optimisation problem using Integer Linear Programming (ILP). This paper explores how the performance of ILP-based Bayesian network learning can be improved through ILP techniques and in particular through the addition of non-essential, implied constraints. There are exponentially many such constraints that can be added to the problem. This paper explores how these constraints may best be generated and added as needed. The results show that using these constraints in the best discovered configuration can lead to a significant improvement in performance and show significant improvement in speed using a state-of-the-art Bayesian network structure learner.


BARTLETT, M. and CUSSENS, J. 2017. Integer linear programming for the Bayesian network structure learning problem. Artificial intelligence [online], 244, pages 258-271. Available from:

Journal Article Type Article
Acceptance Date Mar 7, 2015
Online Publication Date Mar 10, 2015
Publication Date Mar 17, 2017
Deposit Date Jan 20, 2020
Publicly Available Date Jan 20, 2020
Journal Artificial Intelligence
Print ISSN 0004-3702
Electronic ISSN 1872-7921
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 244
Pages 258-271
Keywords Bayesian networks; Integer linear programming; Constrained optimisation; Cutting planes; Separation
Public URL


You might also like

Downloadable Citations