Skip to content

Benchmark Results - Problem U4 - 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.79 msec ± 0.3% 27.59 msec ± 0.5% 33.86 msec ± 0.5% 39.09 msec ± 0.4% 30.78 msec ± 0.4% 31.96 msec ± 0.6% 30.86 msec ± 0.5% 30.78 msec ± 0.6% 31.66 msec ± 0.5% 31.78 msec ± 0.5% 85.33 msec ± 0.7% 110.8 msec ± 0.7% 115.7 msec ± 1.8%
2 200 20 0 24.99 msec ± 0.5% 29.42 msec ± 0.9% 36.56 msec ± 0.6% 42.21 msec ± 0.5% 32.93 msec ± 0.5% 34.15 msec ± 0.3% 33.14 msec ± 0.3% 32.86 msec ± 0.6% 33.80 msec ± 0.8% 33.90 msec ± 0.7% 91.56 msec ± 0.6% 123.1 msec ± 2.8% 129.8 msec ± 3.2%
3 300 30 0 26.47 msec ± 0.7% 31.01 msec ± 1.1% 39.10 msec ± 0.7% 45.73 msec ± 1.0% 35.26 msec ± 0.6% 36.61 msec ± 0.9% 35.52 msec ± 0.8% 34.79 msec ± 0.7% 36.14 msec ± 0.8% 36.06 msec ± 0.8% 96.58 msec ± 0.7% 135.5 msec ± 1.3% 144.1 msec ± 3.6%
4 400 40 0 27.18 msec ± 0.7% 32.18 msec ± 1.3% 41.16 msec ± 1.0% 48.06 msec ± 0.8% 36.88 msec ± 0.6% 37.89 msec ± 1.1% 36.89 msec ± 1.1% 35.94 msec ± 0.4% 37.95 msec ± 1.1% 37.50 msec ± 1.1% 100.9 msec ± 0.9% 144.8 msec ± 1.6% 161.2 msec ± 2.6%
6 600 60 0 29.76 msec ± 0.9% 35.57 msec ± 1.8% 46.88 msec ± 0.7% 55.06 msec ± 0.9% 41.05 msec ± 1.1% 42.06 msec ± 0.8% 41.27 msec ± 1.2% 40.22 msec ± 0.8% 42.21 msec ± 1.4% 42.23 msec ± 1.3% 112.1 msec ± 0.7% 163.2 msec ± 1.5% 188.8 msec ± 4.0%
8 800 80 0 32.12 msec ± 1.6% 38.56 msec ± 1.7% 51.48 msec ± 1.3% 60.82 msec ± 1.1% 44.73 msec ± 1.6% 46.00 msec ± 1.4% 45.04 msec ± 1.6% 43.14 msec ± 1.1% 45.42 msec ± 0.5% 45.38 msec ± 1.2% 121.4 msec ± 0.7% 178.6 msec ± 1.8% 207.1 msec ± 4.1%
12 1200 120 0 36.22 msec ± 1.3% 44.84 msec ± 2.0% 60.37 msec ± 1.9% 72.05 msec ± 1.4% 52.70 msec ± 0.6% 53.84 msec ± 1.6% 52.71 msec ± 1.3% 50.42 msec ± 0.9% 53.49 msec ± 1.9% 52.04 msec ± 1.4% 139.9 msec ± 0.8% 207.3 msec ± 1.4% 274.3 msec ± 6.6%
16 1600 160 0 41.36 msec ± 2.8% 50.70 msec ± 2.1% 67.77 msec ± 1.9% 81.86 msec ± 1.6% 59.64 msec ± 1.9% 59.25 msec ± 2.5% 58.83 msec ± 2.0% 57.22 msec ± 1.8% 58.76 msec ± 1.9% 60.40 msec ± 1.6% 160.8 msec ± 1.2% 246.1 msec ± 0.8% 317.7 msec ± 5.0%
24 2400 240 0 47.00 msec ± 4.2% 58.42 msec ± 2.8% 85.32 msec ± 1.6% 102.9 msec ± 1.2% 74.47 msec ± 2.6% 73.42 msec ± 3.1% 74.92 msec ± 3.1% 70.22 msec ± 1.1% 72.53 msec ± 0.9% 71.56 msec ± 1.0% 199.5 msec ± 0.9% 316.3 msec ± 3.2% 419.7 msec ± 4.1%
32 3200 320 0 57.62 msec ± 0.4% 70.61 msec ± 0.3% 104.8 msec ± 0.7% 132.6 msec ± 0.5% 87.21 msec ± 2.1% 88.34 msec ± 0.6% 88.63 msec ± 0.2% 85.66 msec ± 0.6% 88.38 msec ± 0.5% 87.72 msec ± 2.2% 248.8 msec ± 0.9% 408.4 msec ± 1.3% 527.0 msec ± 5.9%
48 4800 480 0 78.50 msec ± 2.1% 96.07 msec ± 0.7% 149.5 msec ± 0.0% 197.7 msec ± 1.0% 122.5 msec ± 2.6% 123.8 msec ± 1.3% 124.4 msec ± 1.0% 123.0 msec ± 2.4% 123.9 msec ± 1.1% 123.8 msec ± 2.9% 366.5 msec ± 1.3% 598.6 msec ± 1.2% 771.2 msec ± 4.4%
64 6400 640 0 113.6 msec ± 1.2% 126.9 msec ± 2.8% 217.4 msec ± 1.5% 289.3 msec ± 1.2% 167.6 msec ± 0.8% 170.3 msec ± 0.9% 174.8 msec ± 2.4% 154.4 msec ± 1.5% 164.1 msec ± 1.6% 166.9 msec ± 1.4% 532.0 msec ± 1.1% 875.1 msec ± 2.2% 1.187 sec ± 6.1%
Geomean: 39.58 msec ± 1.4% 47.35 msec ± 1.5% 65.03 msec ± 1.0% 78.63 msec ± 1.0% 56.30 msec ± 1.3% 57.39 msec ± 1.2% 56.75 msec ± 1.3% 54.73 msec ± 1.0% 56.91 msec ± 1.1% 56.85 msec ± 1.4% 157.1 msec ± 0.9% 234.0 msec ± 1.7% 280.9 msec ± 4.3%

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.120 ± 1.4% 0.122 ± 1.9% 0.120 ± 1.4% 0.116 ± 1.0% 0.121 ± 1.0% 0.121 ± 1.0% 0.117 ± 1.5% 0.121 ± 2.5% 0.121 ± 2.1% 0.123 ± 0.8% 0.123 ± 1.4% 0.121 ± 0.8% 0.123 ± 1.0%
2 200 20 0 0.160 ± 0.7% 0.169 ± 1.5% 0.161 ± 2.4% 0.157 ± 1.4% 0.166 ± 1.7% 0.166 ± 1.7% 0.161 ± 1.2% 0.170 ± 1.1% 0.170 ± 2.1% 0.170 ± 1.3% 0.174 ± 0.9% 0.175 ± 1.0% 0.175 ± 1.2%
3 300 30 0 0.204 ± 0.8% 0.212 ± 1.5% 0.202 ± 0.9% 0.196 ± 0.7% 0.210 ± 1.5% 0.210 ± 1.5% 0.199 ± 1.3% 0.219 ± 2.4% 0.216 ± 1.6% 0.219 ± 1.3% 0.225 ± 1.0% 0.226 ± 0.8% 0.226 ± 1.3%
4 400 40 0 0.238 ± 0.8% 0.246 ± 0.8% 0.234 ± 1.1% 0.230 ± 1.2% 0.244 ± 0.5% 0.244 ± 0.5% 0.235 ± 0.9% 0.256 ± 0.6% 0.251 ± 0.7% 0.250 ± 0.6% 0.260 ± 0.6% 0.259 ± 0.5% 0.259 ± 0.6%
6 600 60 0 0.290 ± 0.9% 0.301 ± 0.7% 0.287 ± 0.6% 0.285 ± 1.1% 0.297 ± 0.6% 0.297 ± 0.6% 0.289 ± 1.0% 0.311 ± 0.4% 0.305 ± 0.4% 0.304 ± 0.7% 0.316 ± 0.6% 0.316 ± 0.3% 0.315 ± 0.5%
8 800 80 0 0.337 ± 0.6% 0.344 ± 0.4% 0.332 ± 0.6% 0.330 ± 0.4% 0.343 ± 0.3% 0.343 ± 0.3% 0.332 ± 0.3% 0.358 ± 0.3% 0.350 ± 0.5% 0.348 ± 0.5% 0.361 ± 0.3% 0.361 ± 0.3% 0.361 ± 0.2%
12 1200 120 0 0.411 ± 0.3% 0.422 ± 0.2% 0.411 ± 0.3% 0.408 ± 0.3% 0.418 ± 0.2% 0.418 ± 0.2% 0.410 ± 0.4% 0.437 ± 0.3% 0.428 ± 0.3% 0.423 ± 0.3% 0.441 ± 0.3% 0.441 ± 0.2% 0.440 ± 0.2%
16 1600 160 0 0.476 ± 0.2% 0.487 ± 0.2% 0.474 ± 0.2% 0.474 ± 0.3% 0.482 ± 0.4% 0.482 ± 0.4% 0.474 ± 0.2% 0.503 ± 0.2% 0.493 ± 0.2% 0.486 ± 0.3% 0.507 ± 0.1% 0.507 ± 0.1% 0.508 ± 0.2%
24 2400 240 0 0.586 ± 0.2% 0.599 ± 0.2% 0.586 ± 0.1% 0.587 ± 0.2% 0.594 ± 0.1% 0.594 ± 0.1% 0.588 ± 0.1% 0.619 ± 0.1% 0.604 ± 0.1% 0.597 ± 0.2% 0.622 ± 0.1% 0.622 ± 0.0% 0.624 ± 0.1%
32 3200 320 0 0.682 ± 0.1% 0.697 ± 0.1% 0.684 ± 0.1% 0.685 ± 0.2% 0.691 ± 0.0% 0.691 ± 0.0% 0.682 ± 0.1% 0.718 ± 0.1% 0.701 ± 0.1% 0.694 ± 0.1% 0.719 ± 0.2% 0.720 ± 0.1% 0.722 ± 0.1%
48 4800 480 0 0.845 ± 0.0% 0.860 ± 0.1% 0.846 ± 0.1% 0.850 ± 0.0% 0.853 ± 0.1% 0.853 ± 0.1% 0.849 ± 0.0% 0.884 ± 0.0% 0.864 ± 0.1% 0.855 ± 0.0% 0.880 ± 0.1% 0.881 ± 0.1% 0.887 ± 0.1%
64 6400 640 0 0.983 ± 0.1% 0.997 ± 0.0% 0.982 ± 0.0% 0.987 ± 0.1% 0.992 ± 0.1% 0.992 ± 0.1% 0.987 ± 0.1% 1.022 ± 0.0% 1.001 ± 0.1% 0.992 ± 0.1% 1.012 ± 0.1% 1.017 ± 0.1% 1.024 ± 0.1%
Geomean: 0.367 ± 0.5% 0.377 ± 0.6% 0.365 ± 0.6% 0.362 ± 0.6% 0.373 ± 0.5% 0.373 ± 0.5% 0.365 ± 0.6% 0.387 ± 0.7% 0.381 ± 0.7% 0.379 ± 0.5% 0.391 ± 0.5% 0.391 ± 0.4% 0.392 ± 0.5%