uai14-pr
Description
The uai14 solvers are amalgam belief propagation based solvers created for the UAI-2014 competition by Alex Ihler. They begin by reparameterizing the model using loopy BP, then build a series of generalized BP reparameterizations whose outer regions are selected via mini-bucket, eventually transitioning, when there is much more time than memory to cutset conditioning of GBP approximations.
Authors
Alex Ihler
The results below are organized as follows:
- each table displays the solver’s normalized score for individual problem instances (and, for PR, MPE, and MMAP, the associated log10 likelihood value) for the task under different time limits
- table values are normalized scores for each evaluated problem as outlined in Evaluation Criteria
PR
overall
| Problem | 20sec | 1200sec | 3600sec |
|---|---|---|---|
| 1a7w | 100.0 (-1.0) | 100.0 (-1.0) | 100.0 (-1.0) |
| 1aie | 100.0 (2.8) | 100.0 (2.8) | 100.0 (2.8) |
| 1b2v | 100.0 (-53.4) | 100.0 (-53.4) | 100.0 (-53.4) |
| 1bxv | 100.0 (-9.7) | 100.0 (-9.7) | 100.0 (-9.7) |
| 1cpq | 100.0 (-21.7) | 100.0 (-21.7) | 100.0 (-21.7) |
| 1ctj | 100.0 (-13.3) | 100.0 (-13.3) | 100.0 (-13.3) |
| 1cxy | 100.0 (-38.0) | 100.0 (-38.0) | 100.0 (-38.0) |
| 1f94 | 100.0 (-61.4) | 100.0 (-61.4) | 100.0 (-61.4) |
| 1fas | 100.0 (-33.3) | 100.0 (-33.3) | 100.0 (-33.3) |
| 1g6x | 100.0 (-27.2) | 100.0 (-27.2) | 100.0 (-27.2) |
| 1jer | 100.0 (-31.5) | 100.0 (-31.5) | 100.0 (-31.5) |
| 1kp6 | 100.0 (-45.1) | 100.0 (-45.1) | 100.0 (-45.1) |
| 1nkd | 100.0 (-8.8) | 100.0 (-8.8) | 100.0 (-8.8) |
| 1npl | 100.0 (-42.9) | 100.0 (-42.9) | 100.0 (-42.9) |
| 1qt9 | 100.0 (-59.7) | 100.0 (-59.7) | 100.0 (-59.7) |
| 1rfs | 100.0 (-50.6) | 100.0 (-50.6) | 100.0 (-50.6) |
| 1svy | 100.0 (-38.6) | 100.0 (-38.6) | 100.0 (-38.6) |
| 1vfy | 100.0 (-20.1) | 100.0 (-20.1) | 100.0 (-20.1) |
| 2rta | 100.0 (-55.2) | 100.0 (-55.2) | 100.0 (-55.2) |
| BN_12 | 100.0 (-3.6) | 100.0 (-3.6) | 100.0 (-3.6) |
| BN_13 | 100.0 (-2.3) | 100.0 (-2.3) | 100.0 (-2.3) |
| BN_15 | 100.0 (-5.7) | 100.0 (-5.7) | 100.0 (-5.7) |
| BN_31 | 100.0 (-11.0) | 100.0 (-11.0) | 100.0 (-11.0) |
| BN_74 | 100.0 (0.0) | 100.0 (0.0) | 100.0 (0.0) |
| blockmap_10_01-0006 | 74.3 (23.5) | 100.0 (-1.0) | 100.0 (-1.0) |
| blockmap_10_01-0009 | 0.0 (5.6) | 100.0 (-1.0) | 100.0 (-1.0) |
| blockmap_10_02-0009 | 40.1 (6.2) | 100.0 (-2.2) | 100.0 (-2.2) |
| blockmap_10_03-0009 | 0.0 (0.5) | 100.0 (-3.2) | 100.0 (-3.2) |
| blockmap_10_03-0010 | 11.2 (7.3) | 100.0 (-2.9) | 100.0 (-2.9) |
| blockmap_15_01-0008 | 0.0 (111.1) | 100.0 (-1.2) | 100.0 (-1.2) |
| blockmap_15_02-0008 | 0.0 (55.0) | 100.0 (-2.4) | 100.0 (-2.4) |
| blockmap_15_03-0008 | 0.0 (300.0) | 91.7 (-0.5) | 91.7 (-0.5) |
| blockmap_15_03-0010 | 0.0 (160.5) | 100.0 (-3.1) | 100.0 (-3.1) |
| blockmap_20_01-0009 | 0.0 (39.5) | 100.0 (-1.3) | 100.0 (-1.3) |
| blockmap_20_02-0009 | 0.0 (690.4) | 0.0 (482.0) | 0.0 (168.0) |
| blockmap_20_03-0010 | 0.0 (610.9) | 0.0 (323.4) | 0.0 (131.2) |
| blockmap_22_01-0006 | 0.0 (807.5) | 0.0 (539.7) | 0.0 (449.1) |
| blockmap_22_03-0009 | 0.0 (-76.6) | 0.0 (-208.2) | 0.0 (-242.5) |
| bwt3ac.wcsp | 99.6 (-0.0) | 100.0 (0.0) | 100.0 (0.0) |
| fs-07 | 100.0 (-14.8) | 100.0 (-14.8) | 100.0 (-14.8) |
| mastermind_03_08_04-0000 | 100.0 (0.0) | 100.0 (0.0) | 100.0 (0.0) |
| mastermind_03_08_04-0001 | 100.0 (-12.7) | 100.0 (-12.7) | 100.0 (-12.7) |
| mastermind_03_08_04-0002 | 100.0 (-14.5) | 100.0 (-14.5) | 100.0 (-14.5) |
| mastermind_03_08_04-0003 | 100.0 (-11.5) | 100.0 (-11.5) | 100.0 (-11.5) |
| mastermind_03_08_04-0007 | 100.0 (-16.6) | 100.0 (-16.6) | 100.0 (-16.6) |
| mastermind_03_08_04-0008 | 100.0 (-16.3) | 100.0 (-16.3) | 100.0 (-16.3) |
| mastermind_03_08_04-0010 | 99.6 (-15.2) | 100.0 (-14.5) | 100.0 (-14.5) |
| mastermind_03_08_04-0011 | 99.4 (-11.3) | 96.3 (-0.8) | 90.9 (12.5) |
| mastermind_03_08_04-0012 | 99.7 (-8.9) | 90.5 (15.0) | 96.3 (0.9) |
| mastermind_03_08_04-0013 | 99.4 (-10.1) | 99.0 (-6.3) | 99.2 (-6.6) |
| mastermind_03_08_04-0014 | 99.7 (-9.6) | 99.8 (-8.5) | 92.1 (10.3) |
| mastermind_03_08_04-0015 | 99.7 (-8.8) | 99.6 (-7.2) | 99.6 (-7.0) |
| mastermind_03_08_05-0000 | 100.0 (-0.0) | 100.0 (-0.0) | 100.0 (0.0) |
| mastermind_03_08_05-0001 | 100.0 (-15.4) | 100.0 (-15.4) | 100.0 (-15.4) |
| mastermind_03_08_05-0003 | 100.0 (-15.1) | 100.0 (-15.1) | 100.0 (-15.1) |
| mastermind_03_08_05-0004 | 100.0 (-14.2) | 100.0 (-14.2) | 100.0 (-14.3) |
| mastermind_03_08_05-0008 | 99.9 (-14.3) | 100.0 (-14.6) | 100.0 (-14.6) |
| mastermind_03_08_05-0009 | 86.4 (-14.8) | 100.0 (-21.5) | 100.0 (-21.5) |
| mastermind_03_08_05-0011 | 98.6 (-15.9) | 98.7 (-5.0) | 93.3 (16.8) |
| mastermind_03_08_05-0012 | 98.7 (-14.6) | 99.9 (-9.6) | 99.9 (-9.5) |
| mastermind_03_08_05-0013 | 98.9 (-13.5) | 99.8 (-8.0) | 99.8 (-8.1) |
| mastermind_03_08_05-0014 | 99.2 (-12.5) | 98.4 (-2.5) | 98.0 (-1.2) |
| mastermind_03_08_05-0015 | 98.9 (-14.3) | 99.4 (-7.8) | 98.7 (-4.9) |
| mastermind_04_08_03-0000 | 100.0 (-0.0) | 100.0 (-0.0) | 100.0 (-0.0) |
| mastermind_04_08_03-0011 | 99.8 (-5.0) | 100.0 (-4.7) | 100.0 (-4.7) |
| mastermind_04_08_03-0012 | 99.9 (-6.1) | 100.0 (-6.0) | 100.0 (-6.0) |
| mastermind_04_08_03-0013 | 99.9 (-7.3) | 100.0 (-7.2) | 100.0 (-7.2) |
| mastermind_04_08_03-0014 | 99.6 (-7.0) | 100.0 (-6.5) | 100.0 (-6.5) |
| mastermind_04_08_03-0015 | 99.9 (-7.2) | 100.0 (-7.1) | 100.0 (-7.1) |
| mastermind_04_08_04-0000 | 100.0 (0.1) | 100.0 (0.0) | 100.0 (0.0) |
| mastermind_04_08_04-0001 | 100.0 (-11.7) | 100.0 (-11.7) | 100.0 (-11.7) |
| mastermind_04_08_04-0002 | 100.0 (-12.1) | 100.0 (-12.1) | 100.0 (-12.1) |
| mastermind_04_08_04-0003 | 100.0 (-13.6) | 100.0 (-13.6) | 100.0 (-13.6) |
| mastermind_04_08_04-0004 | 100.0 (-11.2) | 100.0 (-11.2) | 100.0 (-11.2) |
| mastermind_04_08_04-0005 | 100.0 (-15.9) | 100.0 (-15.9) | 100.0 (-15.9) |
| mastermind_04_08_04-0011 | 99.3 (-10.3) | 99.7 (-7.6) | 98.8 (-5.2) |
| mastermind_04_08_04-0012 | 99.7 (-8.7) | 93.6 (9.0) | 94.3 (7.3) |
| mastermind_04_08_04-0013 | 98.8 (-10.3) | 99.5 (-5.9) | 98.8 (-4.0) |
| mastermind_04_08_04-0014 | 99.3 (-10.6) | 99.9 (-8.5) | 96.9 (-0.6) |
| mastermind_04_08_04-0015 | 99.0 (-10.3) | 99.9 (-8.0) | 99.9 (-8.1) |
| mastermind_05_08_03-0000 | 100.0 (0.0) | 100.0 (0.0) | 100.0 (0.0) |
| mastermind_05_08_03-0001 | 100.0 (-9.8) | 100.0 (-9.8) | 100.0 (-9.8) |
| mastermind_05_08_03-0002 | 100.0 (-12.2) | 100.0 (-12.2) | 100.0 (-12.2) |
| mastermind_05_08_03-0003 | 100.0 (-8.6) | 100.0 (-8.6) | 100.0 (-8.6) |
| mastermind_05_08_03-0004 | 100.0 (-11.6) | 100.0 (-11.6) | 100.0 (-11.6) |
| mastermind_05_08_03-0009 | 99.7 (-8.3) | 100.0 (-8.0) | 100.0 (-8.0) |
| mastermind_05_08_03-0011 | 99.9 (-6.3) | 99.9 (-6.2) | 100.0 (-6.2) |
| mastermind_05_08_03-0012 | 99.9 (-7.8) | 100.0 (-7.6) | 100.0 (-7.6) |
| mastermind_05_08_03-0013 | 99.8 (-6.3) | 99.8 (-6.2) | 100.0 (-6.6) |
| mastermind_05_08_03-0014 | 99.9 (-4.8) | 100.0 (-4.9) | 100.0 (-4.9) |
| mastermind_05_08_03-0015 | 99.9 (-6.1) | 100.0 (-6.2) | 100.0 (-6.3) |
| mastermind_06_08_03-0000 | 100.0 (-0.0) | 100.0 (0.0) | 100.0 (-0.0) |
| mastermind_06_08_03-0001 | 100.0 (-12.6) | 100.0 (-12.6) | 100.0 (-12.6) |
| mastermind_06_08_03-0002 | 100.0 (-10.5) | 100.0 (-10.5) | 100.0 (-10.5) |
| mastermind_06_08_03-0003 | 100.0 (-11.2) | 100.0 (-11.2) | 100.0 (-11.2) |
| mastermind_06_08_03-0005 | 100.0 (-11.9) | 100.0 (-11.9) | 100.0 (-11.9) |
| mastermind_06_08_03-0009 | 99.9 (-8.5) | 100.0 (-8.3) | 100.0 (-8.4) |
| mastermind_06_08_03-0011 | 99.1 (-6.1) | 99.4 (-5.6) | 99.7 (-5.2) |
| mastermind_06_08_03-0012 | 100.0 (-5.8) | 99.9 (-5.8) | 99.9 (-5.8) |
| mastermind_06_08_03-0014 | 99.9 (-6.2) | 99.9 (-6.2) | 99.9 (-6.2) |
| mastermind_06_08_03-0015 | 99.9 (-7.6) | 99.9 (-7.7) | 99.9 (-7.6) |
| mastermind_10_08_03-0001 | 100.0 (-13.6) | 100.0 (-13.6) | 100.0 (-13.6) |
| mastermind_10_08_03-0003 | 100.0 (-15.5) | 100.0 (-15.6) | 100.0 (-15.5) |
| mastermind_10_08_03-0004 | 100.0 (-16.5) | 100.0 (-16.5) | 100.0 (-16.5) |
| mastermind_10_08_03-0008 | 79.0 (-25.3) | 100.0 (-23.2) | 100.0 (-23.2) |
| mastermind_10_08_03-0009 | 89.7 (-21.5) | 89.0 (-21.7) | 89.0 (-21.7) |
| mastermind_10_08_03-0010 | 99.9 (-10.1) | 99.8 (-9.9) | 99.8 (-9.9) |
| myciel5g_3.wcsp | 75.7 (-42.9) | 94.6 (-57.2) | 94.6 (-57.2) |
| myciel5g_4.wcsp | 59.4 (4.4) | 50.7 (7.0) | 50.8 (7.0) |
| or_chain_1.fg | 92.2 (-11.2) | 93.1 (-11.2) | 93.0 (-11.2) |
| or_chain_102.fg | 90.6 (-10.5) | 92.6 (-10.4) | 91.6 (-10.5) |
| or_chain_106.fg | 93.0 (-10.5) | 93.7 (-10.5) | 94.8 (-10.4) |
| or_chain_107.fg | 97.0 (-11.8) | 97.7 (-11.7) | 99.4 (-11.6) |
| or_chain_12.fg | 93.8 (-12.7) | 95.5 (-12.6) | 95.8 (-12.5) |
| or_chain_128.fg | 93.8 (-11.4) | 96.4 (-11.2) | 96.2 (-11.2) |
| or_chain_132.fg | 100.0 (-8.4) | 100.0 (-8.4) | 100.0 (-8.4) |
| or_chain_138.fg | 100.0 (-10.1) | 100.0 (-10.1) | 100.0 (-10.1) |
| or_chain_140.fg | 88.7 (-6.2) | 93.9 (-5.9) | 91.7 (-6.0) |
| or_chain_149.fg | 100.0 (-8.6) | 100.0 (-8.6) | 100.0 (-8.6) |
| or_chain_15.fg | 99.7 (-11.9) | 99.8 (-11.9) | 99.9 (-11.9) |
| or_chain_150.fg | 97.2 (-7.4) | 99.5 (-7.3) | 99.6 (-7.3) |
| or_chain_153.fg | 95.9 (-9.0) | 99.4 (-8.7) | 100.0 (-8.7) |
| or_chain_155.fg | 100.0 (-10.0) | 99.9 (-9.9) | 100.0 (-10.0) |
| or_chain_161.fg | 97.3 (-9.4) | 99.7 (-9.3) | 100.0 (-9.2) |
| or_chain_186.fg | 97.3 (-9.6) | 99.1 (-9.5) | 100.0 (-9.5) |
| or_chain_188.fg | 99.2 (-12.4) | 100.0 (-12.3) | 100.0 (-12.3) |
| or_chain_198.fg | 99.9 (-4.3) | 100.0 (-4.3) | 100.0 (-4.3) |
| or_chain_209.fg | 98.9 (-11.5) | 100.0 (-11.5) | 100.0 (-11.5) |
| or_chain_242.fg | 98.9 (-5.4) | 98.9 (-5.4) | 100.0 (-5.4) |
| or_chain_4.fg | 97.1 (-11.9) | 99.5 (-11.8) | 98.6 (-11.6) |
| or_chain_53.fg | 100.0 (-9.2) | 100.0 (-9.2) | 100.0 (-9.2) |
| or_chain_61.fg | 97.1 (-8.2) | 97.2 (-8.2) | 97.1 (-8.2) |
| or_chain_64.fg | 93.5 (-9.3) | 100.0 (-8.8) | 100.0 (-8.8) |
| or_chain_90.fg | 88.8 (-9.3) | 95.3 (-8.8) | 95.3 (-8.8) |
| pedigree51 | 96.0 (-74.5) | 94.6 (-73.6) | 95.1 (-73.9) |
| queen5_5_3.wcsp | 79.8 (-88.7) | 99.9 (-113.1) | 100.0 (-113.0) |
| queen5_5_4.wcsp | 64.7 (-25.3) | 83.4 (-36.1) | 83.4 (-36.1) |
| rus2_20_40_0_1 | 0.0 (309.0) | 100.0 (106.9) | 99.9 (106.9) |
| rus2_20_40_0_2 | 0.0 (318.0) | 100.0 (120.6) | 99.9 (120.7) |
| rus2_20_40_0_3 | 0.0 (276.2) | 100.0 (88.2) | 100.0 (88.2) |
| rus2_20_40_1_1 | 0.0 (289.2) | 100.0 (107.4) | 100.0 (107.4) |
| rus2_20_40_1_2 | 0.0 (248.4) | 100.0 (104.5) | 100.0 (104.5) |
| rus2_20_40_1_3 | 0.0 (260.4) | 99.9 (101.7) | 99.9 (101.7) |
| rus2_20_40_2_1 | 0.0 (288.6) | 99.3 (119.7) | 99.7 (119.4) |
| rus2_20_40_2_2 | 0.0 (318.0) | 98.8 (119.2) | 100.0 (118.6) |
| rus2_20_40_2_3 | 0.0 (323.5) | 99.8 (112.6) | 97.6 (110.9) |
| rus2_20_40_3_1 | 0.0 (283.7) | 100.0 (110.2) | 99.3 (109.7) |
| rus2_20_40_3_2 | 0.0 (320.2) | 97.6 (139.7) | 97.6 (139.6) |
| rus2_20_40_3_3 | 0.0 (311.1) | 99.1 (124.1) | 99.3 (123.1) |
| rus2_20_40_4_1 | 0.0 (250.0) | 100.0 (99.2) | 100.0 (99.2) |
| rus2_20_40_4_2 | 0.0 (346.9) | 100.0 (107.1) | 100.0 (107.1) |
| rus2_20_40_4_3 | 0.0 (287.4) | 100.0 (95.2) | 100.0 (95.2) |
| rus2_20_40_5_1 | 0.0 (238.3) | 94.7 (92.3) | 91.2 (90.3) |
| rus2_20_40_5_2 | 0.0 (223.8) | 98.8 (89.2) | 99.8 (88.5) |
| rus2_20_40_5_3 | 0.0 (298.2) | 100.0 (169.9) | 100.0 (169.9) |
| rus2_20_40_6_1 | 0.0 (307.9) | 95.3 (116.1) | 95.2 (116.1) |
| rus2_20_40_6_2 | 0.0 (283.7) | 100.0 (68.4) | 100.0 (68.4) |
| rus2_20_40_6_3 | 0.0 (345.4) | 100.0 (134.1) | 100.0 (134.1) |
| rus2_20_40_7_1 | 0.0 (285.3) | 100.0 (88.5) | 99.9 (88.5) |
| rus2_20_40_7_2 | 0.0 (245.2) | 100.0 (111.5) | 100.0 (111.5) |
| rus2_20_40_7_3 | 0.0 (261.1) | 100.0 (81.4) | 100.0 (81.4) |
| rus2_20_40_8_1 | 0.0 (330.5) | 100.0 (106.9) | 95.1 (103.4) |
| rus2_20_40_8_2 | 0.0 (326.2) | 99.9 (99.9) | 99.9 (99.8) |
| rus2_20_40_8_3 | 0.0 (399.2) | 99.5 (100.9) | 100.0 (100.6) |
| rus2_20_40_9_1 | 0.0 (274.0) | 100.0 (94.5) | 100.0 (94.5) |
| rus2_20_40_9_2 | 0.0 (306.3) | 100.0 (94.6) | 100.0 (94.6) |
| rus2_20_40_9_3 | 0.0 (302.3) | 99.9 (63.5) | 99.9 (63.6) |
| rus_20_40_0_1 | 0.0 (2460.3) | 100.0 (617.3) | 100.0 (617.3) |
| rus_20_40_0_2 | 0.0 (2444.7) | 100.0 (791.6) | 100.0 (791.6) |
| rus_20_40_0_3 | 0.0 (2451.4) | 100.0 (903.0) | 96.5 (896.2) |
| rus_20_40_1_1 | 0.0 (2431.7) | 100.0 (1004.6) | 99.5 (1003.8) |
| rus_20_40_1_2 | 0.0 (2423.0) | 94.7 (920.2) | 100.0 (910.1) |
| rus_20_40_1_3 | 0.0 (2449.3) | 95.9 (892.7) | 98.1 (896.8) |
| rus_20_40_2_1 | 0.0 (2440.0) | 94.9 (807.8) | 99.6 (797.0) |
| rus_20_40_2_2 | 0.0 (2462.3) | 99.5 (688.3) | 100.0 (689.3) |
| rus_20_40_2_3 | 0.0 (2483.3) | 100.0 (749.3) | 100.0 (749.3) |
| rus_20_40_3_1 | 0.0 (2463.3) | 99.6 (825.1) | 100.0 (825.8) |
| rus_20_40_3_2 | 0.0 (2467.5) | 99.8 (838.6) | 99.9 (838.8) |
| rus_20_40_3_3 | 0.0 (2475.0) | 99.8 (841.5) | 99.9 (841.7) |
| rus_20_40_4_1 | 0.0 (2474.3) | 100.0 (931.5) | 95.2 (922.7) |
| rus_20_40_4_2 | 0.0 (2426.5) | 99.3 (934.4) | 99.3 (934.4) |
| rus_20_40_4_3 | 0.0 (2427.9) | 91.1 (871.1) | 96.2 (845.6) |
| rus_20_40_5_1 | 0.0 (2484.6) | 99.8 (875.5) | 99.9 (875.7) |
| rus_20_40_5_2 | 0.0 (2422.6) | 100.0 (839.7) | 100.0 (839.7) |
| rus_20_40_5_3 | 0.0 (2424.4) | 98.5 (878.8) | 98.5 (878.8) |
| rus_20_40_6_1 | 0.0 (2465.4) | 99.2 (725.6) | 99.9 (723.6) |
| rus_20_40_6_2 | 0.0 (2425.2) | 100.0 (982.4) | 99.5 (981.6) |
| rus_20_40_6_3 | 0.0 (2436.3) | 96.7 (960.6) | 100.0 (966.7) |
| rus_20_40_7_1 | 0.0 (2408.4) | 98.6 (754.8) | 100.0 (752.1) |
| rus_20_40_7_2 | 0.0 (2435.3) | 99.4 (755.0) | 99.4 (755.0) |
| rus_20_40_7_3 | 0.0 (2468.7) | 100.0 (869.7) | 100.0 (869.7) |
| rus_20_40_8_1 | 0.0 (2474.1) | 99.4 (725.6) | 98.6 (729.8) |
| rus_20_40_8_2 | 0.0 (2439.9) | 100.0 (898.6) | 99.6 (897.8) |
| rus_20_40_8_3 | 0.0 (2468.2) | 98.9 (701.8) | 100.0 (703.8) |
| rus_20_40_9_1 | 0.0 (2458.6) | 99.2 (868.1) | 90.5 (849.4) |
| rus_20_40_9_2 | 0.0 (2479.3) | 94.9 (823.8) | 100.0 (834.5) |
| rus_20_40_9_3 | 0.0 (2404.9) | 94.7 (874.0) | 99.6 (863.2) |