Skip to content

Benchmark Results - Problem U1 - Optimization Strategies

Tested Optimization strategies (1000 iterations):

name class params
RS OptimRandomSwaps
GS(1) OptimGuidedSwaps min_swap_size=1
max_swap_size=1
GS(2) OptimGuidedSwaps min_swap_size=2
max_swap_size=2
GS(3) OptimGuidedSwaps min_swap_size=3
max_swap_size=3
GS(1-3) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
GS(1-3,soft) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
constraint_softness=ease_in_out(1.00,0.00)
p_add_constraint_aware=ease_in_out(0.00,1.00)
GS(1-3,wide) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
remove_selectivity_modifier=-0.8
add_selectivity_modifier=-0.8
GS(1-3,narrow) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
remove_selectivity_modifier=0.8
add_selectivity_modifier=0.8
GS(1-3,wi->na) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
remove_selectivity_modifier=linear(-0.80,0.80)
add_selectivity_modifier=linear(-0.80,0.80)
GS(1-3,na->wi) OptimGuidedSwaps min_swap_size=1
max_swap_size=3
remove_selectivity_modifier=linear(0.80,-0.80)
add_selectivity_modifier=linear(0.80,-0.80)
SM(2) OptimSmartSwaps swap_size_max=2
nc_remove_max=2
nc_add_max=2
tau_learn=10
ignore_infeasible_diversity_up_to_fraction=0.8
cost_awareness=0.5
SM(4) OptimSmartSwaps swap_size_max=4
nc_remove_max=4
nc_add_max=4
tau_learn=10
ignore_infeasible_diversity_up_to_fraction=0.8
cost_awareness=0.5
SM(8) OptimSmartSwaps swap_size_max=8
nc_remove_max=8
nc_add_max=8
tau_learn=10
ignore_infeasible_diversity_up_to_fraction=0.8
cost_awareness=0.5

Time Duration

d n k m RS GS(1) GS(2) GS(3) GS(1-3) GS(1-3,soft) GS(1-3,wide) GS(1-3,narrow) GS(1-3,wi->na) GS(1-3,na->wi) SM(2) SM(4) SM(8)
1 100 10 0 23.82 msec ± 0.5% 27.65 msec ± 0.6% 33.96 msec ± 0.3% 39.07 msec ± 0.5% 30.85 msec ± 0.5% 32.02 msec ± 0.6% 30.81 msec ± 0.4% 30.85 msec ± 0.5% 31.85 msec ± 0.6% 31.72 msec ± 0.5% 85.70 msec ± 0.5% 110.8 msec ± 1.3% 117.3 msec ± 1.8%
2 200 20 0 25.25 msec ± 0.4% 29.27 msec ± 0.7% 37.05 msec ± 0.8% 42.74 msec ± 0.6% 33.22 msec ± 0.4% 34.22 msec ± 0.4% 33.43 msec ± 0.5% 32.77 msec ± 0.4% 34.15 msec ± 0.6% 34.02 msec ± 0.7% 91.59 msec ± 1.2% 124.3 msec ± 1.6% 132.7 msec ± 1.6%
3 300 30 0 26.16 msec ± 0.4% 30.90 msec ± 0.8% 39.01 msec ± 0.7% 45.36 msec ± 0.9% 35.23 msec ± 1.0% 36.49 msec ± 1.1% 35.55 msec ± 0.9% 34.66 msec ± 0.6% 35.97 msec ± 0.7% 35.87 msec ± 1.1% 96.52 msec ± 1.0% 133.8 msec ± 1.7% 147.7 msec ± 2.7%
4 400 40 0 26.98 msec ± 0.1% 32.45 msec ± 1.3% 40.88 msec ± 1.0% 47.74 msec ± 0.6% 36.91 msec ± 0.9% 37.61 msec ± 0.6% 36.59 msec ± 1.2% 36.03 msec ± 0.6% 37.62 msec ± 0.6% 37.37 msec ± 1.2% 101.3 msec ± 0.5% 144.2 msec ± 1.6% 161.6 msec ± 3.7%
6 600 60 0 29.53 msec ± 0.9% 35.95 msec ± 1.7% 45.79 msec ± 1.1% 54.16 msec ± 0.9% 40.80 msec ± 1.2% 41.50 msec ± 1.5% 40.83 msec ± 1.6% 40.47 msec ± 0.8% 41.61 msec ± 1.3% 41.64 msec ± 1.2% 112.3 msec ± 0.9% 164.2 msec ± 2.1% 192.8 msec ± 4.6%
8 800 80 0 31.42 msec ± 0.6% 38.62 msec ± 1.4% 49.83 msec ± 1.5% 58.85 msec ± 1.2% 43.37 msec ± 0.7% 44.62 msec ± 1.0% 44.08 msec ± 1.3% 43.11 msec ± 0.6% 44.59 msec ± 1.3% 44.75 msec ± 0.8% 120.5 msec ± 0.7% 177.0 msec ± 1.9% 213.8 msec ± 4.2%
12 1200 120 0 34.35 msec ± 1.7% 43.29 msec ± 1.9% 56.91 msec ± 1.6% 67.18 msec ± 1.6% 49.04 msec ± 1.5% 50.12 msec ± 1.9% 49.65 msec ± 1.7% 49.00 msec ± 1.4% 50.83 msec ± 0.8% 50.72 msec ± 1.8% 136.1 msec ± 0.8% 204.6 msec ± 2.0% 256.2 msec ± 6.8%
16 1600 160 0 38.12 msec ± 2.0% 47.28 msec ± 2.4% 64.95 msec ± 0.3% 74.44 msec ± 1.8% 56.25 msec ± 1.5% 57.46 msec ± 0.6% 55.57 msec ± 2.4% 54.79 msec ± 1.7% 56.48 msec ± 1.7% 57.11 msec ± 2.0% 153.6 msec ± 1.3% 235.5 msec ± 1.9% 302.3 msec ± 7.1%
24 2400 240 0 42.83 msec ± 0.8% 55.28 msec ± 4.2% 76.11 msec ± 2.7% 96.57 msec ± 4.1% 67.67 msec ± 3.9% 66.81 msec ± 1.8% 67.77 msec ± 3.7% 66.27 msec ± 3.8% 70.81 msec ± 3.2% 67.05 msec ± 3.5% 188.0 msec ± 2.0% 291.8 msec ± 2.5% 373.8 msec ± 2.6%
32 3200 320 0 51.97 msec ± 0.3% 67.23 msec ± 0.3% 99.41 msec ± 4.3% 117.5 msec ± 2.9% 81.40 msec ± 0.3% 82.51 msec ± 0.3% 80.76 msec ± 0.4% 83.11 msec ± 1.1% 82.19 msec ± 0.9% 83.36 msec ± 1.0% 232.9 msec ± 3.7% 372.9 msec ± 3.7% 508.9 msec ± 4.2%
48 4800 480 0 73.49 msec ± 0.8% 95.56 msec ± 0.8% 149.5 msec ± 1.1% 181.2 msec ± 1.2% 118.1 msec ± 1.5% 122.3 msec ± 2.1% 116.2 msec ± 0.6% 126.1 msec ± 3.7% 120.0 msec ± 1.3% 120.4 msec ± 1.1% 330.9 msec ± 0.8% 553.9 msec ± 2.4% 773.2 msec ± 3.4%
64 6400 640 0 101.0 msec ± 2.1% 127.9 msec ± 1.9% 198.2 msec ± 1.9% 269.1 msec ± 1.3% 169.9 msec ± 2.4% 172.8 msec ± 0.1% 168.2 msec ± 1.5% 175.3 msec ± 1.2% 172.5 msec ± 0.8% 173.1 msec ± 2.6% 481.3 msec ± 1.3% 786.4 msec ± 3.2% 1.156 sec ± 4.8%
Geomean: 37.80 msec ± 0.9% 46.60 msec ± 1.5% 62.84 msec ± 1.4% 75.04 msec ± 1.5% 54.71 msec ± 1.3% 55.92 msec ± 1.0% 54.67 msec ± 1.4% 54.71 msec ± 1.4% 55.96 msec ± 1.2% 55.79 msec ± 1.5% 151.9 msec ± 1.2% 225.9 msec ± 2.1% 276.7 msec ± 4.0%

Diversity Score

d n k m RS GS(1) GS(2) GS(3) GS(1-3) GS(1-3,soft) GS(1-3,wide) GS(1-3,narrow) GS(1-3,wi->na) GS(1-3,na->wi) SM(2) SM(4) SM(8)
1 100 10 0 0.101 ± 0.8% 0.104 ± 0.4% 0.100 ± 1.5% 0.099 ± 2.1% 0.103 ± 0.9% 0.103 ± 0.9% 0.100 ± 1.1% 0.101 ± 1.6% 0.102 ± 1.5% 0.104 ± 0.9% 0.105 ± 0.8% 0.105 ± 0.9% 0.105 ± 0.7%
2 200 20 0 0.219 ± 2.3% 0.230 ± 1.8% 0.218 ± 1.7% 0.213 ± 1.8% 0.232 ± 1.4% 0.232 ± 1.4% 0.217 ± 1.6% 0.236 ± 1.0% 0.235 ± 1.2% 0.235 ± 1.6% 0.239 ± 1.3% 0.243 ± 0.9% 0.240 ± 1.0%
3 300 30 0 0.328 ± 0.8% 0.344 ± 1.0% 0.327 ± 1.2% 0.317 ± 1.1% 0.338 ± 0.9% 0.338 ± 0.9% 0.323 ± 1.6% 0.359 ± 1.6% 0.352 ± 1.2% 0.350 ± 1.2% 0.364 ± 1.3% 0.365 ± 0.9% 0.364 ± 1.0%
4 400 40 0 0.430 ± 0.5% 0.447 ± 0.9% 0.428 ± 1.3% 0.416 ± 1.0% 0.443 ± 0.6% 0.443 ± 0.6% 0.425 ± 1.0% 0.473 ± 1.0% 0.463 ± 1.1% 0.461 ± 0.9% 0.481 ± 0.4% 0.478 ± 0.7% 0.478 ± 0.3%
6 600 60 0 0.593 ± 0.6% 0.619 ± 0.9% 0.590 ± 1.1% 0.586 ± 0.9% 0.610 ± 0.8% 0.610 ± 0.8% 0.588 ± 0.6% 0.653 ± 0.8% 0.633 ± 0.6% 0.631 ± 0.4% 0.658 ± 0.5% 0.656 ± 0.4% 0.659 ± 0.5%
8 800 80 0 0.727 ± 0.7% 0.759 ± 0.4% 0.728 ± 0.5% 0.717 ± 1.0% 0.750 ± 0.4% 0.750 ± 0.4% 0.721 ± 0.7% 0.803 ± 0.3% 0.776 ± 0.6% 0.773 ± 0.3% 0.810 ± 0.3% 0.809 ± 0.3% 0.806 ± 0.5%
12 1200 120 0 0.969 ± 0.5% 1.007 ± 0.6% 0.971 ± 0.4% 0.960 ± 0.6% 0.995 ± 0.6% 0.995 ± 0.6% 0.958 ± 0.6% 1.068 ± 0.3% 1.031 ± 0.3% 1.025 ± 0.4% 1.077 ± 0.4% 1.078 ± 0.2% 1.079 ± 0.3%
16 1600 160 0 1.159 ± 0.4% 1.206 ± 0.5% 1.157 ± 0.3% 1.158 ± 0.2% 1.187 ± 0.3% 1.187 ± 0.3% 1.159 ± 0.3% 1.281 ± 0.3% 1.232 ± 0.4% 1.213 ± 0.6% 1.286 ± 0.1% 1.287 ± 0.1% 1.289 ± 0.3%
24 2400 240 0 1.485 ± 0.1% 1.531 ± 0.4% 1.484 ± 0.4% 1.490 ± 0.2% 1.513 ± 0.4% 1.513 ± 0.4% 1.484 ± 0.2% 1.631 ± 0.3% 1.562 ± 0.3% 1.538 ± 0.2% 1.631 ± 0.2% 1.637 ± 0.2% 1.641 ± 0.2%
32 3200 320 0 1.755 ± 0.1% 1.812 ± 0.2% 1.747 ± 0.1% 1.759 ± 0.1% 1.790 ± 0.1% 1.790 ± 0.1% 1.758 ± 0.3% 1.930 ± 0.1% 1.836 ± 0.2% 1.808 ± 0.1% 1.922 ± 0.3% 1.925 ± 0.1% 1.938 ± 0.2%
48 4800 480 0 2.218 ± 0.2% 2.275 ± 0.0% 2.200 ± 0.1% 2.229 ± 0.1% 2.246 ± 0.1% 2.246 ± 0.1% 2.231 ± 0.2% 2.409 ± 0.1% 2.287 ± 0.2% 2.265 ± 0.1% 2.365 ± 0.1% 2.369 ± 0.0% 2.392 ± 0.2%
64 6400 640 0 2.602 ± 0.1% 2.665 ± 0.1% 2.579 ± 0.2% 2.610 ± 0.0% 2.633 ± 0.0% 2.633 ± 0.0% 2.619 ± 0.1% 2.796 ± 0.1% 2.670 ± 0.1% 2.642 ± 0.1% 2.740 ± 0.1% 2.753 ± 0.2% 2.776 ± 0.2%
Geomean: 0.730 ± 0.6% 0.757 ± 0.6% 0.727 ± 0.7% 0.721 ± 0.8% 0.749 ± 0.5% 0.749 ± 0.5% 0.726 ± 0.7% 0.793 ± 0.6% 0.769 ± 0.6% 0.765 ± 0.6% 0.797 ± 0.5% 0.798 ± 0.4% 0.800 ± 0.4%