Skip to content

Benchmark Results - Problem U3 - 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.87 msec ± 0.7% 27.76 msec ± 0.4% 34.03 msec ± 0.6% 39.07 msec ± 0.4% 30.85 msec ± 0.7% 32.03 msec ± 0.7% 31.10 msec ± 0.5% 31.00 msec ± 0.6% 31.95 msec ± 0.5% 31.86 msec ± 0.5% 86.66 msec ± 0.9% 112.3 msec ± 1.9% 116.3 msec ± 2.3%
2 200 20 0 25.07 msec ± 0.5% 29.43 msec ± 0.6% 36.71 msec ± 0.5% 42.23 msec ± 0.4% 33.04 msec ± 0.7% 34.20 msec ± 0.6% 33.28 msec ± 0.5% 32.82 msec ± 0.6% 34.02 msec ± 0.6% 33.85 msec ± 0.4% 91.55 msec ± 0.7% 124.9 msec ± 1.5% 132.2 msec ± 1.9%
3 300 30 0 26.22 msec ± 0.6% 31.27 msec ± 0.6% 38.98 msec ± 0.5% 45.37 msec ± 0.5% 35.08 msec ± 0.7% 36.08 msec ± 1.1% 35.27 msec ± 0.8% 34.75 msec ± 0.5% 36.02 msec ± 0.6% 35.69 msec ± 0.6% 96.80 msec ± 0.6% 135.7 msec ± 3.5% 147.9 msec ± 2.6%
4 400 40 0 26.93 msec ± 0.6% 32.47 msec ± 1.2% 41.11 msec ± 0.8% 48.02 msec ± 0.8% 36.46 msec ± 1.2% 37.91 msec ± 0.6% 36.82 msec ± 0.9% 36.14 msec ± 0.9% 37.79 msec ± 1.1% 37.19 msec ± 0.8% 100.5 msec ± 0.8% 145.9 msec ± 1.8% 157.0 msec ± 4.4%
6 600 60 0 29.38 msec ± 0.7% 35.77 msec ± 1.4% 45.97 msec ± 1.2% 53.39 msec ± 0.9% 40.45 msec ± 0.9% 41.97 msec ± 1.2% 40.19 msec ± 0.9% 40.07 msec ± 1.4% 41.76 msec ± 0.7% 40.92 msec ± 1.5% 112.3 msec ± 0.8% 166.5 msec ± 1.7% 197.3 msec ± 4.8%
8 800 80 0 30.75 msec ± 0.7% 37.75 msec ± 1.1% 50.04 msec ± 1.2% 58.55 msec ± 0.8% 43.73 msec ± 1.2% 44.97 msec ± 1.3% 43.42 msec ± 1.4% 43.15 msec ± 0.9% 44.35 msec ± 1.7% 43.88 msec ± 1.0% 121.2 msec ± 0.8% 180.4 msec ± 1.4% 217.3 msec ± 3.7%
12 1200 120 0 33.92 msec ± 1.2% 43.52 msec ± 1.3% 56.34 msec ± 1.6% 68.03 msec ± 0.7% 50.03 msec ± 1.7% 50.19 msec ± 1.6% 48.53 msec ± 1.7% 49.40 msec ± 0.9% 50.80 msec ± 0.9% 50.40 msec ± 1.5% 139.6 msec ± 1.3% 210.1 msec ± 1.2% 268.1 msec ± 3.8%
16 1600 160 0 38.26 msec ± 1.5% 46.95 msec ± 2.3% 62.93 msec ± 1.5% 75.03 msec ± 1.7% 55.65 msec ± 0.9% 56.01 msec ± 2.2% 55.34 msec ± 2.2% 56.71 msec ± 1.4% 55.18 msec ± 1.4% 56.31 msec ± 2.3% 158.5 msec ± 1.9% 246.6 msec ± 1.5% 322.7 msec ± 3.8%
24 2400 240 0 46.86 msec ± 5.5% 57.32 msec ± 4.7% 79.66 msec ± 4.5% 90.59 msec ± 0.7% 67.37 msec ± 4.0% 70.65 msec ± 2.2% 66.47 msec ± 4.7% 69.44 msec ± 3.9% 66.45 msec ± 3.5% 72.37 msec ± 3.0% 205.4 msec ± 1.2% 322.9 msec ± 2.1% 458.1 msec ± 2.8%
32 3200 320 0 51.49 msec ± 0.3% 68.98 msec ± 2.0% 95.03 msec ± 2.7% 118.4 msec ± 2.2% 81.55 msec ± 0.5% 82.52 msec ± 0.3% 80.09 msec ± 0.3% 84.55 msec ± 0.6% 83.63 msec ± 3.1% 82.81 msec ± 0.6% 245.7 msec ± 2.2% 414.3 msec ± 1.4% 594.3 msec ± 3.5%
48 4800 480 0 72.35 msec ± 0.4% 96.72 msec ± 1.5% 135.1 msec ± 1.4% 176.3 msec ± 0.6% 116.4 msec ± 0.9% 117.8 msec ± 1.3% 116.3 msec ± 1.2% 123.2 msec ± 1.1% 120.1 msec ± 2.4% 116.0 msec ± 0.3% 339.3 msec ± 1.2% 600.6 msec ± 3.2% 822.1 msec ± 5.2%
64 6400 640 0 109.0 msec ± 2.4% 137.7 msec ± 1.3% 200.5 msec ± 1.9% 267.3 msec ± 1.1% 169.4 msec ± 1.6% 162.2 msec ± 2.1% 163.7 msec ± 0.5% 174.2 msec ± 1.6% 174.9 msec ± 2.0% 163.6 msec ± 2.0% 462.6 msec ± 1.8% 840.0 msec ± 1.8% 1.155 sec ± 8.9%
Geomean: 38.12 msec ± 1.3% 47.14 msec ± 1.5% 62.19 msec ± 1.5% 74.44 msec ± 0.9% 54.56 msec ± 1.3% 55.67 msec ± 1.3% 54.17 msec ± 1.3% 55.08 msec ± 1.2% 55.72 msec ± 1.5% 55.36 msec ± 1.2% 154.4 msec ± 1.2% 235.5 msec ± 1.9% 289.2 msec ± 3.9%

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.949 ± 1.9% 0.969 ± 0.8% 0.939 ± 0.8% 0.912 ± 1.5% 0.969 ± 0.8% 0.969 ± 0.8% 0.941 ± 1.5% 0.960 ± 1.2% 0.966 ± 1.0% 0.971 ± 0.8% 0.972 ± 0.6% 0.973 ± 0.8% 0.969 ± 0.8%
2 200 20 0 1.923 ± 2.2% 2.053 ± 1.0% 1.944 ± 2.0% 1.873 ± 1.5% 1.979 ± 2.0% 1.979 ± 2.0% 1.926 ± 2.2% 2.059 ± 1.6% 2.058 ± 1.7% 2.061 ± 1.0% 2.123 ± 0.6% 2.111 ± 1.2% 2.110 ± 1.3%
3 300 30 0 2.968 ± 0.9% 3.125 ± 0.9% 3.017 ± 1.0% 2.915 ± 1.1% 3.116 ± 1.1% 3.116 ± 1.1% 2.917 ± 1.7% 3.232 ± 0.5% 3.207 ± 1.0% 3.197 ± 1.1% 3.250 ± 0.6% 3.271 ± 0.6% 3.264 ± 0.5%
4 400 40 0 3.824 ± 1.1% 4.078 ± 1.2% 3.885 ± 1.2% 3.782 ± 1.0% 4.025 ± 0.8% 4.025 ± 0.8% 3.724 ± 1.3% 4.288 ± 0.5% 4.180 ± 0.6% 4.178 ± 0.8% 4.312 ± 0.5% 4.299 ± 0.8% 4.283 ± 0.5%
6 600 60 0 5.263 ± 1.0% 5.607 ± 0.6% 5.333 ± 1.2% 5.238 ± 1.0% 5.527 ± 0.8% 5.527 ± 0.8% 5.122 ± 0.8% 5.878 ± 0.5% 5.768 ± 0.5% 5.734 ± 0.6% 5.926 ± 0.4% 5.935 ± 0.6% 5.914 ± 0.4%
8 800 80 0 6.384 ± 1.1% 6.821 ± 0.8% 6.463 ± 1.0% 6.451 ± 0.6% 6.749 ± 0.5% 6.749 ± 0.5% 6.310 ± 1.0% 7.259 ± 0.5% 7.063 ± 0.5% 7.024 ± 0.3% 7.300 ± 0.3% 7.287 ± 0.3% 7.280 ± 0.3%
12 1200 120 0 8.304 ± 0.8% 9.002 ± 0.7% 8.502 ± 0.6% 8.525 ± 0.4% 8.825 ± 0.8% 8.825 ± 0.8% 8.247 ± 1.0% 9.667 ± 0.4% 9.374 ± 0.3% 9.230 ± 0.5% 9.722 ± 0.2% 9.715 ± 0.2% 9.716 ± 0.2%
16 1600 160 0 9.855 ± 0.7% 10.739 ± 0.4% 10.093 ± 0.9% 10.180 ± 0.6% 10.599 ± 0.3% 10.599 ± 0.3% 9.994 ± 0.9% 11.716 ± 0.2% 11.234 ± 0.3% 11.020 ± 0.4% 11.739 ± 0.2% 11.802 ± 0.2% 11.781 ± 0.2%
24 2400 240 0 12.480 ± 0.4% 13.536 ± 0.2% 12.590 ± 0.2% 12.795 ± 0.5% 13.167 ± 0.1% 13.167 ± 0.1% 12.558 ± 0.5% 14.894 ± 0.1% 14.024 ± 0.4% 13.620 ± 0.2% 14.879 ± 0.2% 14.945 ± 0.2% 14.962 ± 0.3%
32 3200 320 0 14.404 ± 0.3% 15.733 ± 0.4% 14.619 ± 0.2% 14.937 ± 0.3% 15.328 ± 0.4% 15.328 ± 0.4% 14.712 ± 0.4% 17.542 ± 0.1% 16.215 ± 0.3% 15.745 ± 0.2% 17.371 ± 0.4% 17.414 ± 0.1% 17.565 ± 0.3%
48 4800 480 0 17.734 ± 0.5% 19.236 ± 0.2% 17.913 ± 0.2% 18.558 ± 0.2% 18.840 ± 0.1% 18.840 ± 0.1% 18.233 ± 0.2% 21.860 ± 0.0% 19.847 ± 0.3% 18.966 ± 0.2% 20.572 ± 0.6% 21.016 ± 0.5% 21.403 ± 0.4%
64 6400 640 0 20.416 ± 0.1% 21.913 ± 0.2% 20.688 ± 0.0% 21.544 ± 0.2% 21.468 ± 0.3% 21.468 ± 0.3% 21.147 ± 0.4% 24.883 ± 0.3% 22.356 ± 0.1% 21.552 ± 0.2% 23.237 ± 0.5% 23.817 ± 0.2% 24.423 ± 0.4%
Geomean: 6.272 ± 0.9% 6.715 ± 0.6% 6.352 ± 0.8% 6.340 ± 0.7% 6.601 ± 0.7% 6.601 ± 0.7% 6.276 ± 1.0% 7.181 ± 0.5% 6.895 ± 0.6% 6.790 ± 0.5% 7.143 ± 0.4% 7.177 ± 0.5% 7.198 ± 0.5%