We are concerned with algorithms for solving reasoning problems over graphical models, which includes common tasks for belief, constraint, and mixed networks. In the following we present some of the resulting work; this list is bound to grow over time.
See our Repository for some example problem instances.
Likelihood algorithms
Exact P(e)
These algorithms compute the exact probability of a given set of evidence in a Bayesian network.
aolibPE computes the exact probability of evidence for Bayesian networks using AND/OR search spaces.
Bucket_Elimination performs variable elimination to obtain the exact probability of evidence.
VEC performs variable elimination plus conditioning to obtain the exact probability of evidence.
Approximate P(e)
These algorithms compute the approximate probability of a given set of evidence in a Bayesian network.
IJGPIS computes approximate probability of evidence in Bayesian networks using importance sampling, Iterative Join Graph Propagation (IJGP) and Relational Consistency.
IJGPSampleSearch computes approximate probability of evidence in Bayesian networks using importance sampling, SampleSearch and Iterative Join Graph Propagation (IJGP).
Approximate Belief Updating (or posterior marginals)
These algorithms compute approximate beliefs for each variable in a network, given a certain set of evidence.
IJGP (Iterative Join Graph Propagation) computes approximate beliefs in Bayesian networks.
IJGPIS computes approximate beliefs in Bayesian networks using importance sampling, Iterative Join Graph Propagation (IJGP) and Relational Consistency.
IJGPSampleSearch computes approximate beliefs in Bayesian networks using importance sampling, SampleSearch and Iterative Join Graph Propagation (IJGP).
Compilation of AND/OR Multi-Valued Decision Diagrams (AOMDDs)
This algorithm compiles a weighted CSP or Bayesian network into an AOMDD.
aomdd compiles AOMDDs for weighted CSPs or Bayesian networks using AND/OR search.
Optimization algorithms
MPE
These algorithms compute the most likely tuple in a Bayesian network given some evidence.
aolibMPE implements several exact AND/OR search algorithms to compute the most probable explanation in Bayesian networks using Mini-Bucket heuristics and caching.
mbeMPE implements the Mini-Bucket approximation of the most probable explanation in Bayesian networks.
DAOOPT is a new implementation of AND/OR Branch-and-Bound to solve MPE problems over Bayes and Markov networks. It also offers a Mini-Bucket heuristic, full caching, Breadth-Rotate AOBB for improved anytime performance, as well as stochastic local search for preprocessing. Full source code is available under GPL.
WCSP
These algorithms compute an optimal assignment in a weighted constraint satisfaction problem given some evidence.
aolibWCSP finds the optimal solution to weighted constraint satisfaction problems via various AND/OR search algorithms using Mini-Bucket heuristics and caching.
mbeWCSP implements the Mini-Bucket approximation for weighted constraint satisfaction problems.
ILP
This algorithm computes an optimal solution to an integer programming problem.
aolibILP computes the optimal solution to 0/1 integer linear programs using AND/OR search.
General purpose algorithms
Computing Elimination Orderings
CVO implements the Iterative Greedy Variable Ordering (IGVO) algorithm.
Tree Decomposition
This algorithm decomposes a given graphical model (Bayesian, Markov or constraint network) into a tree decomposition.
quickbb A complete anytime algorithm to compute tree decomposition of a graph.
treeDecomp computes a tree decomposition of a given graphical model.
Older software
REES offers a GUI to create and edit graphical models and implements a number of algorithms. It is no longer actively developed.
Disclaimer: All software should be regarded as in development and is made available on an "as-is" basis, without warranty of any kind. It has in no way been thoroughly tested and might not function as intended or expected.