Vibhav Gogate

QuickBB

Papers

Vibhav Gogate and Rina Dechter, “A complete Anytime Algorithm for Treewidth,” In 20th Conference on Uncertainty in Artificial Intelligence (UAI), 2004. [ PDF ]

Software: Download the binaries

• 64 bit Linux binary

• 32 bit Linux binary

Help

• quickbb [option1] [option2] –cnffile CNFFILE

• A description of the (input) CNF format is given here. Any graph can be written in this format. For example, a chain 1-2-3 can be specified as:

The first line says that we are specifying the graph using 3 variables and 2 cliques (each edge is a clique. Trivially, you can specify a graph using its edges)

The second line describes the first clique between vertex 1 and 2. “0” is the delimiter which specifies end of line.

The third line describes the second clique between vertex 2 and vertex 3.

[option1] should be one of the following:

1. --random-ordering: Branching performed in quickbb using random ordering

2. --min-fill-ordering: Branching performed in quickbb using min-fill ordering

[option2] can be any of the following or combination thereof:

1. --time [int]: Integer time-bound.

2. --lb: Computes lb of the graph,

3. --outfile [filename]: Store the output like treewidth, lb and the current best perfect elimination order (peo).

4. --statfile [filename]: Program statistics. The statfile has the following format:

   1. row1:#vertices,

   2. row2: #edges

   3. row3: lb if --lb is used else 0,

   4. row4: an upper bound on the treewidth

   5. row5: Time elapsed,

   6. row6:Nodes Visited,

   7. row7:Nodes Pruned

   8. row8:1 if the treewidth given in row3 is exact and 0 if it is not.

Example

This will run quickbb on the ls8_normalized.cnf instance. The ordering heuristic used is min-fill. The output will be stored in myout and the statistics will be stored in mystat.