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)

Updated: