## Vibhav Gogate## QuickBB## PapersVibhav Gogate and Rina Dechter, “A complete Anytime Algorithm for Treewidth,” In 20th Conference on Uncertainty in Artificial Intelligence (UAI), 2004. [
## Helpquickbb [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:
p cnf 3 2 1 2 0 2 3 0 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: --random-ordering: Branching performed in quickbb using random ordering --min-fill-ordering: Branching performed in quickbb using min-fill ordering
[option2] can be any of the following or combination thereof: --time [int]: Integer time-bound. --lb: Computes lb of the graph, --outfile [filename]: Store the output like treewidth, lb and the current best perfect elimination order (peo). --statfile [filename]: Program statistics. The statfile has the following format: row1:#vertices, row2: #edges row3: lb if --lb is used else 0, row4: an upper bound on the treewidth row5: Time elapsed, row6:Nodes Visited, row7:Nodes Pruned row8:1 if the treewidth given in row3 is exact and 0 if it is not.
## Example/quickbb_64 –min-fill-ordering –lb –outfile myout –statfile mystat –cnffile ls8_normalized.cnf
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 |