Vibhav Gogate

Iterative Join Graph Propagation

Papers

• Robert Mattescu, Kalev Kask, Vibhav Gogate and Rina Dechter, “Join-Graph Propagation Algorithms/,” Journal of Artificial Intelligence Research, 2010. [ PDF ].

Software: Download the binaries

• 64 bit Linux binary.

• 32 bit Linux binary.

Help

Caution! IJGP is run as an anytime scheme. Therefore, it may eat your linux swap space, if the problem is hard. To set proper time and memory limits use the ulimit command. For example, use: “ulimit -v 2097152” to limit the amount of memory available to 2 Gigabytes. To run the solver with default options, just type:

The uai08file and the uai08evidfile should be in UAI 2008 format. The description of this format is available here.

The output will be stored in < uai08file > .MAR in the working directory. Note that after each i-bound, the results are written to the output file. [http:www.cs.huji.ac.ilprojectUAI10/fileFormat.php

How to set the options:

1. --i-bound [int] (default value is 0. The starting i-bound used by IJGP.)

2. --num-iterations [int] (default value is 10. The number of iterations for which IJGP is run.)

3. --order [min-fill|min-degree|lex] (default value is min-fill. The ordering heuristic used to construct the join graph.)

4. --num-tries [int] (The orderings are randomized. default value is 1. If set to a value greater than 1, then we run the ordering heuristic a number of times and select the one that yields the smallest treewidth.)

Example

This will run ijgp on the specified files. The join-graphs will be constructed using the min-degree ordering. The starting i-bound is 3. Note that IJGP is run as an anytime scheme. In this case, we will start with an i-bound of 3, run IJGP until convergence or 100 iterations whichever is earlier. Then we increase the i-bound by one and reconstruct the join graph, iteratively repeating the process until we run out of memory or time.