Advances in Bayesian Network Learning using Integer Programming

James Cussens, Mark Bartlett
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:85-94, 2013.

Abstract

We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-cussens13a, title = {Advances in {B}ayesian Network Learning using Integer Programming}, author = {Cussens, James and Bartlett, Mark}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {85--94}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/cussens13a/cussens13a.pdf}, url = {https://proceedings.mlr.press/r11/cussens13a.html}, abstract = {We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Advances in Bayesian Network Learning using Integer Programming %A James Cussens %A Mark Bartlett %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-cussens13a %I PMLR %P 85--94 %U https://proceedings.mlr.press/r11/cussens13a.html %V R11 %X We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results. %Z Reissued by PMLR on 04 October 2026.
APA
Cussens, J. & Bartlett, M.. (2013). Advances in Bayesian Network Learning using Integer Programming. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:85-94 Available from https://proceedings.mlr.press/r11/cussens13a.html. Reissued by PMLR on 04 October 2026.

Related Material