Description

Toulbar2-VACINT uses an initial upper bound solution found by INCOP local search. Next, the solver enforces Virtual Arc Consistency in preprocessing. A hybrid best-first search method is performed, restarting from the root after a given backtrack number and following VAC-integrality/Full-EAC variable ordering heuristic. The solver also applies a VAC-based upper bound probing heuristic to find good solutions in preprocessing. Toulbar2

Authors

David Allouche, Simon de Givry, George Katsirelos, Thomas Schiex, and Fulya Trösser

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 0.0 (nan) 100.0 (5520.9) 100.0 (5520.9)
1CM1 0.0 (nan) 100.0 (5414.6) 100.0 (5414.6)
1SY9 0.0 (nan) 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) 36.5 (-1154.2) 100.0 (-1152.5)
BN-d-200-5-10 99.3 (-46.6) 99.3 (-46.6) 99.3 (-46.6)
BN-d-20000-4-2 0.0 (nan) 100.0 (-2338.6) 100.0 (-2338.6)
BN-d-250-5-10 86.5 (-57.6) 86.5 (-57.6) 86.5 (-57.6)
BN-d-500-5-10 61.3 (-121.8) 75.5 (-120.1) 75.5 (-120.1)
BN-nd-10000-4-2 0.0 (nan) 24.9 (-1308.1) 100.0 (-1305.1)
BN-nd-200-5-10 98.2 (-54.6) 98.2 (-54.6) 98.2 (-54.6)
BN-nd-20000-4-2 0.0 (nan) 60.1 (-2574.3) 100.0 (-2573.6)
BN-nd-250-5-10 88.9 (-66.0) 88.9 (-66.0) 88.9 (-66.0)
BN-nd-500-5-10 67.5 (-138.6) 77.3 (-137.5) 77.3 (-137.5)
Maxsat_aes_64_1_keyfind_1 80.9 (1857.4) 84.1 (1859.5) 86.3 (1860.9)
Maxsat_gss-25-s100 0.0 (nan) 49.9 (63302.4) 49.9 (63302.4)
Maxsat_mod2c-rand3bip-sat-240-3.shuffled-as.sat05-2520 79.0 (1626.9) 79.0 (1626.9) 79.0 (1626.9)
Maxsat_mod2c-rand3bip-sat-250-3.shuffled-as.sat05-2535 79.3 (1680.9) 79.3 (1680.9) 79.3 (1680.9)
Maxsat_mod4block_2vars_10gates_u2_autoenc 0.0 (nan) 98.9 (81310.1) 98.9 (81310.1)
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 100.0 (-0.1) 100.0 (-0.1) 100.0 (-0.1)
grid20x20.f10 97.4 (1297.0) 98.5 (1302.6) 98.9 (1304.2)
grid20x20.f10.wrap 97.1 (1310.1) 98.9 (1319.4) 98.9 (1319.4)
grid20x20.f15 98.7 (1952.0) 99.6 (1959.0) 99.6 (1959.0)
grid20x20.f15.wrap 91.8 (1917.7) 98.9 (1973.3) 99.4 (1977.3)
grid20x20.f5.wrap 91.4 (649.3) 98.9 (667.4) 98.9 (667.4)
grid40x40.f10 91.8 (5346.3) 93.0 (5369.6) 93.4 (5376.9)
grid40x40.f10.wrap 95.2 (5563.7) 95.5 (5569.8) 95.5 (5569.8)
grid40x40.f15 94.3 (8066.4) 95.0 (8087.8) 95.0 (8087.8)
grid40x40.f15.wrap 92.7 (8237.7) 94.0 (8285.4) 94.1 (8287.3)
grid40x40.f2 87.4 (1127.2) 87.4 (1127.2) 87.4 (1127.2)
grid40x40.f2.wrap 96.7 (1167.9) 98.3 (1173.5) 98.3 (1173.5)
grid40x40.f5 94.8 (2733.8) 95.8 (2743.1) 95.8 (2743.1)
grid40x40.f5.wrap 93.3 (2757.0) 94.4 (2768.3) 94.7 (2771.1)
grid80x80.f10 77.6 (20079.9) 94.1 (21437.4) 94.3 (21454.1)
grid80x80.f10.wrap 76.2 (20062.1) 95.6 (21654.6) 95.7 (21665.5)
grid80x80.f15 77.5 (29969.1) 93.8 (32021.0) 94.2 (32069.9)
grid80x80.f15.wrap 80.3 (30619.9) 94.5 (32496.1) 94.6 (32512.0)
grid80x80.f2 74.5 (4355.8) 95.3 (4618.0) 95.9 (4625.5)
grid80x80.f2.wrap 76.5 (4409.3) 95.0 (4666.9) 95.2 (4668.6)
grid80x80.f5 75.2 (10237.6) 93.8 (10927.3) 94.2 (10942.4)
grid80x80.f5.wrap 75.3 (10160.6) 94.5 (10902.6) 95.0 (10924.6)
pdb1jmx 100.0 (-501.4) 100.0 (-501.4) 100.0 (-501.4)
pdb1kgn 100.0 (-748.7) 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 98.0 (-126.8) 99.4 (-125.7) 100.0 (-125.3)
pedigree19 97.8 (-99.0) 99.4 (-97.6) 99.5 (-97.6)
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 100.0 (-160.8) 100.0 (-160.8) 100.0 (-160.8)
pedigree30 98.9 (-138.0) 100.0 (-137.0) 100.0 (-137.0)
pedigree31 100.0 (-130.5) 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.3 (-132.8) 99.3 (-130.9) 99.5 (-130.8)
pedigree41 98.6 (-121.9) 100.0 (-120.7) 100.0 (-120.7)
pedigree42 100.0 (-81.8) 100.0 (-81.8) 100.0 (-81.8)
pedigree44 98.5 (-97.8) 100.0 (-97.0) 100.0 (-97.0)
pedigree50 100.0 (-61.7) 100.0 (-61.7) 100.0 (-61.7)
pedigree51 97.9 (-111.7) 100.0 (-109.6) 100.0 (-109.6)
pedigree7 100.0 (-113.9) 100.0 (-113.9) 100.0 (-113.9)
pedigree9 97.9 (-124.8) 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 100.0 (2683.9) 100.0 (2683.9) 100.0 (2683.9)
rus_100_200_2_1 96.7 (2639.4) 96.7 (2639.4) 96.7 (2639.4)
rus_100_200_3_1 85.8 (2539.4) 85.8 (2539.4) 85.8 (2539.4)
rus_100_200_3_3 75.9 (2449.6) 75.9 (2449.6) 75.9 (2449.6)
rus_100_200_4_3 79.2 (2479.5) 79.2 (2479.5) 79.2 (2479.5)
rus_100_200_5_3 89.5 (2573.3) 89.5 (2573.3) 89.5 (2573.3)
rus_100_200_6_1 56.9 (2276.7) 56.9 (2276.7) 56.9 (2276.7)
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 (1338.1) 0.0 (1338.1) 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 99.3 (-14.1) 100.0 (-13.6) 100.0 (-13.6)
scen07.wcsp 99.7 (-1.6) 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: