BBMarkovA Branch-and-Bound Approach for Learning Score-Optimal Chordal Markov networksDeveloped by the Constraint Reasoning and Optimization Group The program learns optimal chordal Markov network structures with respect to given decomposable scoring functions. UsageUsage: ./bbmarkov [flags] <filename> Flags: -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 formatThe 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: 3 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. DownloadsThe program can be downloaded here. Some score files are included as examples. References
[1] Learning Chordal Markov Networks via Branch and Bound. |