Solving Bayesian Network Structure Learning Problem with Integer Linear Programming

This dissertation investigates integer linear programming (ILP) formulation\nof Bayesian Network structure learning problem. We review the definition and\nkey properties of Bayesian network and explain score metrics used to measure\nhow well certain Bayesian network structure fits the dataset. We outline the\ninteger linear programming formulation based on the decomposability of score\nmetrics. In order to ensure acyclicity of the structure, we add ``cluster\nconstraints'' developed specifically for Bayesian network, in addition to cycle\nconstraints applicable to directed acyclic graphs in general. Since there would\nbe exponential number of these constraints if we specify them fully, we explain\nthe methods to add them as cutting planes without declaring them all in the\ninitial model. Also, we develop a heuristic algorithm that finds a feasible\nsolution based on the idea of sink node on directed acyclic graphs. We\nimplemented the ILP formulation and cutting planes as a \\textsf{Python}\npackage, and present the results of experiments with different settings on\nreference datasets.\n