toulbar2-vns-mpe
Description
Toulbar2-VNS is a metaheuristic called variable neighborhood search that uses (partial) tree search inside its local neighborhood exploration. The approach consists of several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit, and the neighborhood size. Thus, the optimality of the obtained solutions can be proven when the neighborhood size is maximal and with an unbounded tree search. The tree decomposition uses a minimum fill-in ordering. Leaf clusters are merged with their fathers if the number of proper variables is too small. Toulbar2
Authors
David Allouche, Simon de Givry, Samir Loudni, and Abdelkader Ouali
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
MPE
overall
| Problem | 20sec | 1200sec | 3600sec |
|---|---|---|---|
| 1CKK | 96.9 (5494.2) | 100.0 (5520.9) | 100.0 (5520.9) |
| 1CM1 | 100.0 (5414.6) | 100.0 (5414.6) | 100.0 (5414.6) |
| 1SY9 | 100.0 (3985.1) | 100.0 (3985.1) | 100.0 (3985.1) |
| 2BBN | 0.0 (nan) | 100.0 (5328.6) | 100.0 (5328.6) |
| 2BCX | 0.0 (nan) | 100.0 (6002.2) | 100.0 (6002.2) |
| BN-d-10000-4-2 | 0.0 (nan) | 0.0 (nan) | 0.0 (nan) |
| BN-d-200-5-10 | 100.0 (-46.5) | 100.0 (-46.5) | 100.0 (-46.5) |
| BN-d-20000-4-2 | 0.0 (nan) | 0.0 (nan) | 0.0 (nan) |
| BN-d-250-5-10 | 92.8 (-57.1) | 100.0 (-56.6) | 100.0 (-56.6) |
| BN-d-500-5-10 | 75.1 (-120.1) | 100.0 (-117.0) | 100.0 (-117.0) |
| BN-nd-10000-4-2 | 0.0 (nan) | 0.0 (nan) | 0.0 (nan) |
| BN-nd-200-5-10 | 99.1 (-54.5) | 99.1 (-54.5) | 99.1 (-54.5) |
| BN-nd-20000-4-2 | 0.0 (nan) | 0.0 (nan) | 0.0 (nan) |
| BN-nd-250-5-10 | 100.0 (-65.3) | 100.0 (-65.3) | 100.0 (-65.3) |
| BN-nd-500-5-10 | 89.6 (-136.1) | 90.8 (-135.9) | 90.8 (-135.9) |
| Maxsat_aes_64_1_keyfind_1 | 92.7 (1864.9) | 95.9 (1867.0) | 95.9 (1867.0) |
| Maxsat_gss-25-s100 | 0.0 (nan) | 73.8 (63435.1) | 84.0 (63492.0) |
| Maxsat_mod2c-rand3bip-sat-240-3.shuffled-as.sat05-2520 | 88.8 (1632.8) | 88.9 (1632.8) | 88.9 (1632.8) |
| Maxsat_mod2c-rand3bip-sat-250-3.shuffled-as.sat05-2535 | 91.5 (1688.0) | 91.5 (1688.0) | 91.5 (1688.0) |
| Maxsat_mod4block_2vars_10gates_u2_autoenc | 0.0 (nan) | 80.8 (81230.7) | 80.8 (81230.7) |
| Promedas_60 | 100.0 (-10.0) | 100.0 (-10.0) | 100.0 (-10.0) |
| Promedas_61 | 100.0 (-6.9) | 100.0 (-6.9) | 100.0 (-6.9) |
| Promedas_62 | 100.0 (-4.7) | 100.0 (-4.7) | 100.0 (-4.7) |
| Promedas_63 | 100.0 (-6.1) | 100.0 (-6.1) | 100.0 (-6.1) |
| Promedas_64 | 100.0 (-11.5) | 100.0 (-11.5) | 100.0 (-11.5) |
| Promedas_65 | 100.0 (-5.2) | 100.0 (-5.2) | 100.0 (-5.2) |
| Promedas_66 | 100.0 (-10.4) | 100.0 (-10.4) | 100.0 (-10.4) |
| Promedas_67 | 100.0 (-13.4) | 100.0 (-13.4) | 100.0 (-13.4) |
| Promedas_68 | 100.0 (-18.9) | 100.0 (-18.9) | 100.0 (-18.9) |
| Promedas_69 | 100.0 (-11.2) | 100.0 (-11.2) | 100.0 (-11.2) |
| driverlog04ac.wcsp | 100.0 (-0.2) | 100.0 (-0.2) | 100.0 (-0.2) |
| driverlog05ac.wcsp | 100.0 (-0.1) | 100.0 (-0.1) | 100.0 (-0.1) |
| driverlog08ac.wcsp | 92.6 (-8.1) | 100.0 (-0.1) | 100.0 (-0.1) |
| grid20x20.f10 | 96.9 (1294.7) | 98.5 (1302.7) | 98.5 (1302.7) |
| grid20x20.f10.wrap | 97.0 (1309.6) | 97.0 (1309.6) | 99.1 (1320.5) |
| grid20x20.f15 | 97.6 (1944.4) | 97.6 (1944.4) | 97.6 (1944.4) |
| grid20x20.f15.wrap | 98.2 (1967.6) | 98.2 (1967.6) | 98.2 (1967.6) |
| grid20x20.f5.wrap | 96.6 (661.9) | 96.6 (661.9) | 96.6 (661.9) |
| grid40x40.f10 | 98.0 (5466.6) | 98.8 (5480.4) | 98.8 (5480.4) |
| grid40x40.f10.wrap | 97.4 (5614.1) | 97.8 (5622.9) | 97.8 (5622.9) |
| grid40x40.f15 | 96.9 (8143.6) | 97.8 (8169.7) | 97.8 (8169.7) |
| grid40x40.f15.wrap | 97.6 (8410.5) | 98.2 (8434.3) | 98.2 (8434.3) |
| grid40x40.f2 | 99.5 (1166.1) | 99.5 (1166.1) | 99.5 (1166.1) |
| grid40x40.f2.wrap | 99.5 (1177.6) | 99.5 (1177.6) | 99.5 (1177.6) |
| grid40x40.f5 | 98.7 (2769.4) | 98.7 (2769.4) | 98.7 (2769.4) |
| grid40x40.f5.wrap | 96.6 (2790.4) | 98.7 (2812.1) | 98.7 (2812.1) |
| grid80x80.f10 | 92.9 (21340.7) | 98.5 (21801.2) | 98.5 (21801.2) |
| grid80x80.f10.wrap | 93.0 (21442.6) | 98.8 (21919.6) | 99.1 (21945.7) |
| grid80x80.f15 | 93.8 (32023.6) | 98.6 (32634.7) | 99.2 (32713.9) |
| grid80x80.f15.wrap | 93.4 (32354.8) | 98.6 (33039.3) | 99.3 (33133.2) |
| grid80x80.f2 | 92.0 (4577.2) | 99.8 (4674.6) | 99.8 (4674.6) |
| grid80x80.f2.wrap | 94.0 (4652.6) | 99.7 (4731.6) | 99.7 (4731.6) |
| grid80x80.f5 | 92.5 (10879.4) | 98.6 (11104.0) | 99.0 (11119.9) |
| grid80x80.f5.wrap | 91.2 (10776.6) | 97.5 (11019.8) | 98.2 (11045.4) |
| pdb1jmx | 100.0 (-501.4) | 100.0 (-501.4) | 100.0 (-501.4) |
| pdb1kgn | 99.8 (-749.2) | 100.0 (-748.7) | 100.0 (-748.7) |
| pdb1kwh | 100.0 (-305.5) | 100.0 (-305.5) | 100.0 (-305.5) |
| pdb1m3y | 100.0 (-1054.2) | 100.0 (-1054.2) | 100.0 (-1054.2) |
| pdb1qks | 100.0 (-657.0) | 100.0 (-657.0) | 100.0 (-657.0) |
| pedigree1 | 100.0 (-45.6) | 100.0 (-45.6) | 100.0 (-45.6) |
| pedigree13 | 100.0 (-73.4) | 100.0 (-73.4) | 100.0 (-73.4) |
| pedigree18 | 100.0 (-125.3) | 100.0 (-125.3) | 100.0 (-125.3) |
| pedigree19 | 94.5 (-101.8) | 96.7 (-99.9) | 99.1 (-97.9) |
| pedigree20 | 100.0 (-53.8) | 100.0 (-53.8) | 100.0 (-53.8) |
| pedigree23 | 100.0 (-62.4) | 100.0 (-62.4) | 100.0 (-62.4) |
| pedigree25 | 99.9 (-160.9) | 100.0 (-160.8) | 100.0 (-160.8) |
| pedigree30 | 99.3 (-137.6) | 100.0 (-137.0) | 100.0 (-137.0) |
| pedigree31 | 99.4 (-131.2) | 100.0 (-130.5) | 100.0 (-130.5) |
| pedigree33 | 100.0 (-74.9) | 100.0 (-74.9) | 100.0 (-74.9) |
| pedigree34 | 100.0 (-111.1) | 100.0 (-111.1) | 100.0 (-111.1) |
| pedigree37 | 100.0 (-144.9) | 100.0 (-144.9) | 100.0 (-144.9) |
| pedigree38 | 100.0 (-87.3) | 100.0 (-87.3) | 100.0 (-87.3) |
| pedigree39 | 100.0 (-155.6) | 100.0 (-155.6) | 100.0 (-155.6) |
| pedigree40 | 97.9 (-132.3) | 99.0 (-131.2) | 99.0 (-131.2) |
| pedigree41 | 98.8 (-121.8) | 100.0 (-120.7) | 100.0 (-120.7) |
| pedigree42 | 100.0 (-81.8) | 100.0 (-81.8) | 100.0 (-81.8) |
| pedigree44 | 98.3 (-98.0) | 98.3 (-97.9) | 99.8 (-97.1) |
| pedigree50 | 100.0 (-61.7) | 100.0 (-61.7) | 100.0 (-61.7) |
| pedigree51 | 99.9 (-109.7) | 99.9 (-109.7) | 100.0 (-109.6) |
| pedigree7 | 100.0 (-113.9) | 100.0 (-113.9) | 100.0 (-113.9) |
| pedigree9 | 96.4 (-126.1) | 100.0 (-122.9) | 100.0 (-122.9) |
| rovers02ac.wcsp | 100.0 (-0.2) | 100.0 (-0.2) | 100.0 (-0.2) |
| rus_100_200_1_1 | 95.2 (2639.6) | 100.0 (2683.9) | 100.0 (2683.9) |
| rus_100_200_2_1 | 94.9 (2622.2) | 96.7 (2639.4) | 96.7 (2639.4) |
| rus_100_200_3_1 | 77.1 (2460.8) | 85.8 (2539.4) | 85.8 (2539.4) |
| rus_100_200_3_3 | 68.6 (2383.2) | 75.9 (2449.6) | 75.9 (2449.6) |
| rus_100_200_4_3 | 74.3 (2434.9) | 79.2 (2479.5) | 79.2 (2479.5) |
| rus_100_200_5_3 | 83.9 (2522.8) | 89.5 (2573.3) | 89.5 (2573.3) |
| rus_100_200_6_1 | 54.2 (2251.7) | 54.4 (2254.0) | 54.4 (2254.0) |
| rus_50_100_4_1 | 39.6 (1535.9) | 39.6 (1535.9) | 39.6 (1535.9) |
| rus_50_100_4_3 | 55.8 (1615.8) | 55.8 (1615.8) | 55.8 (1615.8) |
| rus_50_100_6_1 | 0.0 (1337.8) | 0.0 (1337.8) | 0.0 (1338.1) |
| rus_50_100_6_2 | 64.1 (1656.5) | 64.1 (1656.5) | 64.1 (1656.5) |
| rus_50_100_7_1 | 33.1 (1504.1) | 33.1 (1504.1) | 33.1 (1504.1) |
| rus_50_100_7_2 | 34.2 (1509.9) | 34.2 (1509.9) | 34.2 (1509.9) |
| rus_50_100_8_1 | 21.3 (1446.2) | 21.3 (1446.2) | 21.3 (1446.2) |
| rus_50_100_9_3 | 55.5 (1614.3) | 55.5 (1614.3) | 55.5 (1614.3) |
| satellite01ac.wcsp | 100.0 (-0.1) | 100.0 (-0.1) | 100.0 (-0.1) |
| satellite02ac.wcsp | 100.0 (-0.0) | 100.0 (-0.0) | 100.0 (-0.0) |
| scen06.wcsp | 100.0 (-13.6) | 100.0 (-13.6) | 100.0 (-13.6) |
| scen07.wcsp | 100.0 (-1.4) | 100.0 (-1.4) | 100.0 (-1.4) |
| zenotravel02ac.wcsp | 100.0 (-0.1) | 100.0 (-0.1) | 100.0 (-0.1) |
| zenotravel04ac.wcsp | 100.0 (-0.1) | 100.0 (-0.1) | 100.0 (-0.1) |