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.

DAOOPT-UAI12 is a version of the above solver using MBE code by Alex Ihler. In addition to the features of the DAOOPT, it includes cost-shifting schemes to tighten the problem formulation and the bounds produced by MBE algorithm.

W-SEARCH implements several AND/OR search algorithms that use weighted heuristics to produce a w-optimal approximate solution to a

**most probable explanation**problem in Bayesian or Markov networks, namely a solution guaranteed to be within the factor of w from the optimal (on logarithmic scale).

#### m-best MPE

These algorithms compute the m-most likely tuples and the corresponding probabilities in a Bayesian or Markov network, reporting the solutions in the non-increasing order of the probabilities.

MBE-M-OPT uses Mini-Bucket elimination approach to compute bounds on the

**m-best solutions**to the**most probable explanation**or**MAP**task in Bayesian or Markov networks.M-BEST-SEARCH implements several exact best-first and depth-first branch and bound search algorithms to compute the

**m-best solutions**to a**most probable explanation**in Bayesian or Markov networks using Mini-Bucket heuristics, exploring both OR and AND/OR search spaces.

#### 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.