Benchmark Descriptions
The following sets of benchmarks were used in the evaluation:
 Linkage1 / WCSP
 bn2o
 Diagnose
 Grids
 Linkage 2
 Promedas
 UAI06MPE
 UAI06PE
 Relational
In the following these sets are characterized in more detail.
Linkage1 / WCSP
 Submitter: Thomas Schiex (INRA France)
 Domain: Linkage and converted weighted CSPs
 Type: Linkage is Bayes, others Markov, all for MPE
 9 Linkage: max. domain size 45
 16 Radio Freq.: max. domain size 44
 16 Coloring: max. domain size 5
 18 Planning: max. domain size 27,
 20 Satellite: max. domain size 4
 18 Warehouse: max. domain size 200
 Between ~50500 variables, Satellite and Warehouse up to 1100, Linkage up to 2200.
 Treewidth: many have width ~3060
 weighted CSP networks also submitted as benchmarks for 3rd MaxCSP competition:
bn2o
 Submitter: Jirka Vomlel and Petr Savicky (Academy of Sciences of the Czech Republic)
 Domain: twolayer noisyor Bayesian networks
 Type: Bayes for MAR/PRE
 18 instances
 All variables binary
 45, 50, or 55 variables
 Treewidth: ~2427
 some exact PE solvers run out of memory (given 3GB)
Diagnose
 Submitter: John M. Agosta (Intel Corp.)
 Domain: diagnostic Bayesian networks, handbuilt
 Type: Bayes for MAR
 2 Instances, each with 50 different sets of randomly generated evidence (leaf nodes only)
 I 203 and 359 variables, respectively
 Max. domain size 7 and 6, respectively
 nodes assume causal independence (e.g., noisymax)
 relatively large for networks constructed by hand
 ~200300 nodes, ~300600 edges
 Treewidth ~1118: still easy for exact solvers
Grids
 Submitter: Tian Sang (University of Washington)
 Domain: Grid networks, from 12x12 to 50x50 with varying level of determinism
 Type: Bayes for PRE
 roughly, 50%, 75%, or 90% of the parameters are 0/1
 320 Instances
 Between 144 and 2,500 binary variables
 treewidth: ~1250
 Evidence by assigning value 1 to leaf node
networks, list of networks used for exact PR/MAR, and a subset of networks used for the other tasks.
Linkage 2
 Submitter: Dechter group (UC Irvine)
 Domain: Genetic linkage
 Type: Markov for MPE
 22 instances
 Max. domain size between 3 and 7
 Treewidth: ~2035
Promedas
 Submitter: Vicenc Gomez (University Nijmegen)
 Domain: Medical diagnosis, realworld cases, converted from noisyor
 Type: Markov for MAR/PRE
 238 Instances
 Binary variables
 QMRDT like networks; layered noisyor model
 Bayesian network model converted to Markov network after performing simplifications (pruning unobserved nodes, negative findings, compact representation of noisyor, etc)
 Treewidths range from 1 (tree) to ~60
 most are too difficult for exact algorithms
UAI06MPE and UAI06PE
 Submitter: Used in UAI'06 evaluation
 Domain: Various
 Type: Bayes for MPE and PRE, respectively
 57 MPE instances
78 PRE instances</UL>
 For details, see last UAI evaluation:
Relational
 Submitter: UCLA
 Domain: Relational Bayesian networks constructed from the Primula tool
 Type: Bayes for MAR/PRE
 251 networks, with binary variables
 150 Blockmap: 700 to 59,404 variables
 80 Mastermind: 1,220 to 3,692 variables
11 Friends & Smoker: 10 to 76,212 variables
 10 Students: 376 variables
 Large networks with large treewidths, but with high levels of determinism
networks, list of networks used for exact PR/MAR, and a subset of networks used for the other tasks.
Benchmarks
All benchmarks are available for download here. Lists of networks used, or subsets of networks used, are also given. Note that each network was assigned (arbitrarily) an ID, for purposes of the evaluation.
Networks are specified in the evaluation FileFormat, with accompanying evidence.
Summary tables
These tables summarize the benchmark instances used with exact solvers for MAR and PE.
('Bayes' and 'Markov' show whether the set contains Bayesian or Markov networks, 'Binary' whether the instances have binary variables only.)
Set 

Bayes 
Markov 
Binary 
WeightedCSP 
97 
x 
x 

bn2o 
18 
x 

x 
Diagnosis 
100 
x 


Grids 
320 
x 

x 
Linkage 2 
22 

x 

Promedas 
238 

x 
x 
UAI06MPE 
57 
x 


UAI06PE 
78 
x 


Relational 
251 
x 

x 
TOTAL 
1181 
824 
357 
323 
Due to time constraints, MPE and all approximate solvers were run on a reduced set of instances, as shown in the following table:
Set 

Bayes 
Markov 
Binary 
WeightedCSP 
97 
x 
x 

bn2o 
18 
x 

x 
Diagnosis 
0/100 
x 


Grids 
32/320 
x 

x 
Linkage 2 
22 

x 

Promedas 
238 

x 
x 
UAI06MPE 
57 
x 


UAI06PE 
78 
x 


Relational 
35/251 
x 

x 
TOTAL 
577 
220 
357 
323 