A Branch-and-Bound Approach for Learning Score-Optimal Chordal Markov networks

Developed by the Constraint Reasoning and Optimization Group
at the Department of Computer Science, University of Helsinki,
and implemented by Kari Rantanen.

The program learns optimal chordal Markov network structures with respect to given decomposable scoring functions.
Details on the algorithm can be found at [1].


Usage: ./bbmarkov [flags] <filename>

	-v    Minimal verbosity
	-s    Keep track of the number of recurring skeletons (for debugging purposes)
	-o    Prune recurring option lists
	-t    Use tight upper bounds that take immoralities into consideration
	-f    Fix an arbitrary variable to be the first in the ordering

Recommended flags are -ft. (-o is good with some instances)

Input format

The input is a text file expressing the values of a decomposable scoring function, given in Cussens' file format. The first line is a natural number denoting the number of variables N. What follows is series of domains, expressing the possible parent sets for each of the N variables.

A domain starts with the following line:

<variable ID from 0 to N-1> <number of parent sets>

The succeeding lines list the parent sets and take the following form:

<score of the set> <number of parents> <list of variables in the set>

The variables in the list are separated by spaces. For example, an input file for a 3-variable instance might look like this:

0 4
-195.673828 2 1 2
-194.647797 1 2
-189.098404 1 1
-193.265869 0
1 4
-517.531555 1 2
-587.681213 1 0
-518.557739 2 0 2
-591.848389 0
2 4
-562.807800 2 0 1
-556.232178 1 1
-631.931213 1 0
-630.549072 0

Note: Each domain must contain exactly the same amount of parent sets. With unbounded treewidth, exactly 2^(N - 1) parent sets are needed for each of the N variables. That is, the input cannot be preprocessed with classic score pruning techniques. If you want to bound the treewidth of the problem instance, simply remove all parent sets from the input that contain too many parents.


The program can be downloaded here. Some score files are included as examples.


[1] Learning Chordal Markov Networks via Branch and Bound.
Kari Rantanen, Antti Hyttinen, and Matti Järvisalo.
In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS 2017),
pages ???-???. NIPS, 2017. (to appear)