AbstractionSampling
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) |