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 for- mulated as an integer program (IP). We de- scribe the various steps we have taken to al- low efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (per- haps 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 ear- lier 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 for- mulated as an integer program (IP). We de- scribe the various steps we have taken to al- low efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (per- haps 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 ear- lier 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 for- mulated as an integer program (IP). We de- scribe the various steps we have taken to al- low efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (per- haps 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 ear- lier 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