Description

Abstraction Sampling is an importance-sampling based scheme that serves as a means of interpolation between search and sampling. It draws its inspiration from stratified importance sampling, likewise abstracting similar states together to compactify the search/sampling space. The scheme used here samples over an AND/OR search space, has its proposal guided by a weighted mini-bucket heuristic that utilizes cost-shifting, and forms abstractions based on a randomized subset of nodes’ context assignments (which acts as a proxy for similarity). For this trial, the number of abstract states were limited to 64 abstract states per level in the search tree. More details about this work can be found in the related paper and presentation.

Authors

Kalev Kask, Filjor Broka

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 99.6 (-1.0) 0.0 (nan) 100.0 (-1.0)
1aie 98.8 (2.8) 0.0 (nan) 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) 0.0 (nan)
1cpq 99.7 (-21.7) 0.0 (nan) 100.0 (-21.7)
1ctj 99.9 (-13.3) 100.0 (-13.3) 100.0 (-13.3)
1cxy 100.0 (-38.0) 100.0 (-38.0) 100.0 (-38.0)
1f94 99.9 (-61.4) 0.0 (nan) 100.0 (-61.4)
1fas 0.0 (nan) 100.0 (-33.3) 100.0 (-33.3)
1g6x 99.5 (-27.2) 0.0 (nan) 100.0 (-27.2)
1jer 100.0 (-31.5) 100.0 (-31.5) 100.0 (-31.5)
1kp6 100.0 (-45.1) 0.0 (nan) 0.0 (nan)
1nkd 99.9 (-8.8) 0.0 (nan) 0.0 (nan)
1npl 0.0 (nan) 100.0 (-42.9) 100.0 (-42.9)
1qt9 98.9 (-59.9) 100.0 (-59.7) 99.9 (-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 99.2 (-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 99.9 (-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 99.9 (-10.9) 100.0 (-11.0) 100.0 (-11.0)
BN_74 99.0 (-1.5) 100.0 (-0.0) 100.0 (-0.0)
blockmap_10_01-0006 99.4 (-0.5) 100.0 (-1.0) 100.0 (-1.1)
blockmap_10_01-0009 100.0 (-1.0) 100.0 (-1.0) 100.0 (-1.0)
blockmap_10_02-0009 100.0 (-2.2) 100.0 (-2.2) 100.0 (-2.2)
blockmap_10_03-0009 100.0 (-3.2) 100.0 (-3.2) 100.0 (-3.2)
blockmap_10_03-0010 100.0 (-2.9) 100.0 (-2.9) 100.0 (-2.9)
blockmap_15_01-0008 100.0 (-1.2) 100.0 (-1.2) 100.0 (-1.2)
blockmap_15_02-0008 100.0 (-2.4) 100.0 (-2.4) 100.0 (-2.4)
blockmap_15_03-0008 0.0 (-inf) 100.0 (-3.2) 100.0 (-3.2)
blockmap_15_03-0010 100.0 (-3.1) 100.0 (-3.1) 100.0 (-3.1)
blockmap_20_01-0009 100.0 (-1.3) 100.0 (-1.3) 100.0 (-1.3)
blockmap_20_02-0009 0.0 (nan) 100.0 (-2.6) 100.0 (-2.6)
blockmap_20_03-0010 0.0 (nan) 100.0 (-4.0) 100.0 (-4.0)
blockmap_22_01-0006 0.0 (nan) 100.0 (-1.3) 100.0 (-1.3)
blockmap_22_03-0009 100.0 (-4.1) 100.0 (-4.1) 100.0 (-4.1)
bwt3ac.wcsp 99.8 (0.1) 100.0 (0.0) 99.9 (0.0)
fs-07 100.0 (-14.7) 100.0 (-14.8) 100.0 (-14.8)
mastermind_03_08_04-0000 0.0 (-inf) 100.0 (-0.0) 100.0 (0.0)
mastermind_03_08_04-0001 99.6 (-13.1) 100.0 (-12.7) 100.0 (-12.7)
mastermind_03_08_04-0002 99.8 (-14.6) 100.0 (-14.5) 100.0 (-14.5)
mastermind_03_08_04-0003 99.7 (-11.9) 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.9 (-14.4) 100.0 (-14.5) 100.0 (-14.5)
mastermind_03_08_04-0011 0.0 (-inf) 0.0 (-inf) 100.0 (-9.7)
mastermind_03_08_04-0012 0.0 (-inf) 99.9 (-8.0) 99.9 (-8.0)
mastermind_03_08_04-0013 0.0 (-inf) 99.9 (-8.9) 99.9 (-8.4)
mastermind_03_08_04-0014 0.0 (-inf) 0.0 (-inf) 99.5 (-10.1)
mastermind_03_08_04-0015 0.0 (-inf) 99.1 (-10.3) 99.9 (-7.9)
mastermind_03_08_05-0000 0.0 (-inf) 0.0 (-inf) 99.5 (-2.2)
mastermind_03_08_05-0001 0.0 (-inf) 100.0 (-15.5) 100.0 (-15.5)
mastermind_03_08_05-0003 0.0 (-inf) 100.0 (-15.2) 100.0 (-15.1)
mastermind_03_08_05-0004 0.0 (-inf) 100.0 (-14.3) 100.0 (-14.2)
mastermind_03_08_05-0008 0.0 (-inf) 99.8 (-15.2) 99.8 (-15.3)
mastermind_03_08_05-0009 100.0 (-21.5) 100.0 (-21.5) 100.0 (-21.5)
mastermind_03_08_05-0011 0.0 (-inf) 0.0 (-inf) 0.0 (-inf)
mastermind_03_08_05-0012 0.0 (-inf) 0.0 (-inf) 0.0 (-inf)
mastermind_03_08_05-0013 0.0 (-inf) 0.0 (-inf) 0.0 (-inf)
mastermind_03_08_05-0014 0.0 (-inf) 0.0 (-inf) 0.0 (-inf)
mastermind_03_08_05-0015 0.0 (-inf) 0.0 (-inf) 0.0 (-inf)
mastermind_04_08_03-0000 100.0 (-0.0) 100.0 (0.0) 100.0 (0.0)
mastermind_04_08_03-0011 99.9 (-4.8) 100.0 (-4.7) 100.0 (-4.7)
mastermind_04_08_03-0012 99.9 (-6.2) 100.0 (-6.0) 100.0 (-6.0)
mastermind_04_08_03-0013 100.0 (-7.2) 100.0 (-7.2) 100.0 (-7.2)
mastermind_04_08_03-0014 100.0 (-6.5) 100.0 (-6.5) 100.0 (-6.5)
mastermind_04_08_03-0015 99.8 (-6.9) 100.0 (-7.1) 100.0 (-7.1)
mastermind_04_08_04-0000 0.0 (-inf) 99.9 (-0.3) 99.9 (-0.2)
mastermind_04_08_04-0001 99.2 (-12.5) 100.0 (-11.7) 100.0 (-11.7)
mastermind_04_08_04-0002 98.7 (-14.0) 100.0 (-12.1) 100.0 (-12.1)
mastermind_04_08_04-0003 95.8 (-18.7) 100.0 (-13.6) 100.0 (-13.6)
mastermind_04_08_04-0004 0.0 (-inf) 100.0 (-11.2) 100.0 (-11.2)
mastermind_04_08_04-0005 0.0 (-inf) 100.0 (-16.0) 100.0 (-15.9)
mastermind_04_08_04-0011 0.0 (-inf) 99.3 (-10.3) 99.8 (-7.9)
mastermind_04_08_04-0012 0.0 (-inf) 99.9 (-8.2) 99.6 (-9.1)
mastermind_04_08_04-0013 0.0 (-inf) 99.6 (-8.2) 0.0 (-inf)
mastermind_04_08_04-0014 0.0 (-inf) 99.6 (-7.8) 0.0 (-inf)
mastermind_04_08_04-0015 0.0 (-inf) 98.8 (-10.8) 0.0 (-inf)
mastermind_05_08_03-0000 99.7 (0.5) 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.9 (-8.0) 100.0 (-8.0) 100.0 (-8.0)
mastermind_05_08_03-0011 99.7 (-6.7) 100.0 (-6.2) 100.0 (-6.2)
mastermind_05_08_03-0012 99.5 (-8.3) 100.0 (-7.6) 100.0 (-7.6)
mastermind_05_08_03-0013 99.7 (-6.2) 100.0 (-6.6) 100.0 (-6.6)
mastermind_05_08_03-0014 99.9 (-5.1) 100.0 (-4.9) 100.0 (-4.9)
mastermind_05_08_03-0015 99.3 (-7.4) 100.0 (-6.3) 100.0 (-6.3)
mastermind_06_08_03-0000 0.0 (-inf) 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.3) 100.0 (-8.4) 100.0 (-8.4)
mastermind_06_08_03-0011 99.6 (-4.1) 100.0 (-4.7) 100.0 (-4.7)
mastermind_06_08_03-0012 0.0 (-inf) 100.0 (-5.9) 100.0 (-5.9)
mastermind_06_08_03-0014 0.0 (-inf) 100.0 (-6.3) 100.0 (-6.3)
mastermind_06_08_03-0015 0.0 (-inf) 100.0 (-7.7) 100.0 (-7.7)
mastermind_10_08_03-0001 0.0 (-inf) 100.0 (-13.6) 100.0 (-13.7)
mastermind_10_08_03-0003 0.0 (-inf) 100.0 (-15.5) 100.0 (-15.6)
mastermind_10_08_03-0004 0.0 (-inf) 100.0 (-16.5) 100.0 (-16.5)
mastermind_10_08_03-0008 100.0 (-23.2) 100.0 (-23.2) 100.0 (-23.2)
mastermind_10_08_03-0009 100.0 (-17.8) 100.0 (-17.8) 100.0 (-17.8)
mastermind_10_08_03-0010 0.0 (-inf) 100.0 (-10.1) 100.0 (-10.1)
myciel5g_3.wcsp 92.7 (-66.7) 99.4 (-61.7) 97.4 (-63.1)
myciel5g_4.wcsp 97.9 (-8.7) 98.8 (-8.4) 98.5 (-8.5)
or_chain_1.fg 87.0 (-11.6) 94.3 (-11.1) 95.0 (-11.1)
or_chain_102.fg 96.4 (-9.9) 94.1 (-10.3) 94.1 (-10.3)
or_chain_106.fg 80.0 (-11.4) 95.3 (-10.4) 95.2 (-10.4)
or_chain_107.fg 89.5 (-12.3) 99.0 (-11.5) 99.9 (-11.6)
or_chain_12.fg 72.7 (-14.2) 95.8 (-12.5) 95.8 (-12.5)
or_chain_128.fg 88.7 (-11.8) 96.7 (-11.2) 96.3 (-11.2)
or_chain_132.fg 99.8 (-8.4) 99.9 (-8.4) 100.0 (-8.4)
or_chain_138.fg 99.0 (-10.1) 99.6 (-10.0) 100.0 (-10.1)
or_chain_140.fg 20.0 (-10.3) 77.0 (-6.9) 95.6 (-5.8)
or_chain_149.fg 99.4 (-8.6) 100.0 (-8.6) 100.0 (-8.6)
or_chain_15.fg 81.9 (-13.1) 99.0 (-11.8) 99.9 (-11.9)
or_chain_150.fg 91.9 (-7.5) 99.7 (-7.3) 99.6 (-7.2)
or_chain_153.fg 86.2 (-9.6) 100.0 (-8.7) 100.0 (-8.7)
or_chain_155.fg 95.0 (-10.3) 100.0 (-9.9) 100.0 (-9.9)
or_chain_161.fg 97.6 (-9.1) 99.5 (-9.2) 99.6 (-9.3)
or_chain_186.fg 94.5 (-9.7) 99.9 (-9.5) 100.0 (-9.5)
or_chain_188.fg 97.8 (-12.5) 100.0 (-12.3) 100.0 (-12.3)
or_chain_198.fg 93.9 (-4.6) 99.9 (-4.3) 100.0 (-4.3)
or_chain_209.fg 92.8 (-12.0) 99.9 (-11.5) 99.9 (-11.5)
or_chain_242.fg 98.7 (-5.5) 99.9 (-5.3) 99.9 (-5.3)
or_chain_4.fg 88.4 (-12.5) 100.0 (-11.7) 100.0 (-11.7)
or_chain_53.fg 99.8 (-9.2) 100.0 (-9.2) 100.0 (-9.2)
or_chain_61.fg 92.3 (-8.4) 100.0 (-8.0) 99.2 (-8.0)
or_chain_64.fg 92.2 (-9.4) 100.0 (-8.8) 100.0 (-8.8)
or_chain_90.fg 94.8 (-8.9) 95.3 (-8.8) 95.3 (-8.8)
pedigree51 95.7 (-74.4) 95.0 (-73.9) 95.0 (-73.9)
queen5_5_3.wcsp 98.2 (-115.3) 99.2 (-113.9) 99.7 (-113.4)
queen5_5_4.wcsp 98.9 (-46.3) 95.3 (-48.5) 98.8 (-46.4)
rus2_20_40_0_1 99.9 (106.9) 99.9 (106.9) 100.0 (106.9)
rus2_20_40_0_2 99.9 (120.6) 99.9 (120.6) 100.0 (120.6)
rus2_20_40_0_3 100.0 (88.2) 99.9 (88.2) 100.0 (88.2)
rus2_20_40_1_1 100.0 (107.4) 100.0 (107.4) 100.0 (107.4)
rus2_20_40_1_2 100.0 (104.5) 100.0 (104.5) 100.0 (104.5)
rus2_20_40_1_3 99.8 (101.5) 99.9 (101.6) 100.0 (101.6)
rus2_20_40_2_1 98.6 (118.5) 99.4 (119.0) 99.2 (118.8)
rus2_20_40_2_2 98.2 (117.5) 98.9 (118.0) 97.4 (117.1)
rus2_20_40_2_3 99.9 (112.4) 99.9 (112.3) 99.9 (112.4)
rus2_20_40_3_1 99.3 (110.6) 99.7 (110.0) 99.8 (110.0)
rus2_20_40_3_2 99.9 (141.1) 99.6 (140.9) 100.0 (141.2)
rus2_20_40_3_3 99.8 (123.4) 99.9 (123.5) 99.7 (123.3)
rus2_20_40_4_1 99.9 (99.1) 100.0 (99.2) 100.0 (99.2)
rus2_20_40_4_2 100.0 (107.0) 100.0 (107.0) 100.0 (107.1)
rus2_20_40_4_3 99.9 (95.2) 100.0 (95.2) 100.0 (95.2)
rus2_20_40_5_1 100.0 (95.5) 99.9 (95.4) 100.0 (95.4)
rus2_20_40_5_2 99.7 (88.1) 99.3 (87.8) 100.0 (88.3)
rus2_20_40_5_3 100.0 (169.9) 99.9 (169.9) 100.0 (169.9)
rus2_20_40_6_1 99.7 (118.9) 99.8 (119.3) 99.9 (119.1)
rus2_20_40_6_2 99.9 (68.3) 100.0 (68.4) 100.0 (68.4)
rus2_20_40_6_3 100.0 (134.1) 99.9 (134.2) 100.0 (134.1)
rus2_20_40_7_1 100.0 (88.5) 100.0 (88.5) 100.0 (88.5)
rus2_20_40_7_2 99.9 (111.5) 100.0 (111.6) 100.0 (111.5)
rus2_20_40_7_3 99.9 (81.4) 100.0 (81.4) 100.0 (81.4)
rus2_20_40_8_1 100.0 (106.9) 99.9 (107.0) 100.0 (106.9)
rus2_20_40_8_2 99.9 (99.8) 99.9 (99.9) 100.0 (99.9)
rus2_20_40_8_3 99.9 (100.5) 99.9 (100.5) 99.9 (100.5)
rus2_20_40_9_1 99.9 (94.6) 100.0 (94.5) 100.0 (94.5)
rus2_20_40_9_2 99.4 (94.1) 100.0 (94.6) 100.0 (94.6)
rus2_20_40_9_3 99.9 (63.7) 99.9 (63.7) 99.9 (63.6)
rus_20_40_0_1 100.0 (617.3) 99.9 (617.5) 100.0 (617.4)
rus_20_40_0_2 100.0 (791.6) 100.0 (791.6) 100.0 (791.6)
rus_20_40_0_3 100.0 (903.0) 100.0 (903.0) 100.0 (903.0)
rus_20_40_1_1 100.0 (1004.6) 97.2 (999.7) 97.4 (999.9)
rus_20_40_1_2 100.0 (910.1) 99.4 (911.4) 97.4 (905.4)
rus_20_40_1_3 95.3 (891.4) 95.5 (891.8) 95.4 (891.5)
rus_20_40_2_1 100.0 (797.8) 97.4 (792.8) 97.4 (792.8)
rus_20_40_2_2 97.2 (683.7) 91.1 (671.7) 97.2 (683.8)
rus_20_40_2_3 95.4 (739.8) 93.8 (736.3) 93.8 (736.4)
rus_20_40_3_1 99.8 (825.5) 99.8 (825.5) 99.7 (825.4)
rus_20_40_3_2 100.0 (839.0) 99.9 (838.9) 99.7 (838.4)
rus_20_40_3_3 100.0 (841.9) 95.2 (832.9) 99.8 (841.6)
rus_20_40_4_1 95.2 (922.7) 99.5 (930.6) 99.6 (930.7)
rus_20_40_4_2 99.3 (934.4) 99.7 (935.2) 99.5 (934.9)
rus_20_40_4_3 100.0 (853.3) 95.2 (843.6) 96.7 (846.6)
rus_20_40_5_1 100.0 (875.9) 100.0 (875.9) 99.8 (875.5)
rus_20_40_5_2 100.0 (839.6) 97.9 (835.6) 97.9 (835.5)
rus_20_40_5_3 98.5 (878.8) 98.6 (879.0) 98.4 (878.6)
rus_20_40_6_1 95.1 (713.5) 99.9 (724.0) 100.0 (723.9)
rus_20_40_6_2 100.0 (982.4) 97.3 (977.4) 97.3 (977.4)
rus_20_40_6_3 96.3 (959.9) 94.7 (956.9) 96.7 (960.7)
rus_20_40_7_1 100.0 (752.1) 100.0 (752.1) 100.0 (752.1)
rus_20_40_7_2 100.0 (756.2) 98.7 (753.6) 98.5 (753.3)
rus_20_40_7_3 100.0 (869.7) 97.5 (864.9) 97.5 (864.9)
rus_20_40_8_1 99.5 (725.8) 97.5 (721.8) 99.8 (726.6)
rus_20_40_8_2 100.0 (898.6) 97.3 (893.7) 97.3 (893.7)
rus_20_40_8_3 98.9 (701.8) 96.3 (696.8) 96.3 (696.8)
rus_20_40_9_1 90.5 (849.4) 100.0 (866.6) 100.0 (866.6)
rus_20_40_9_2 93.9 (821.6) 100.0 (834.5) 100.0 (834.5)
rus_20_40_9_3 100.0 (863.9) 99.3 (865.3) 99.7 (864.6)

Updated: