Benchmark Results - Problem U2 - 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 | 24.02 msec ± 0.4% | 27.96 msec ± 0.6% | 34.29 msec ± 0.3% | 39.45 msec ± 0.4% | 31.21 msec ± 0.3% | 32.50 msec ± 0.7% | 31.25 msec ± 0.5% | 31.28 msec ± 0.5% | 32.14 msec ± 0.5% | 32.02 msec ± 0.5% | 86.18 msec ± 0.9% | 112.0 msec ± 2.5% | 117.2 msec ± 2.2% |
| 2 | 200 | 20 | 0 | 25.14 msec ± 0.6% | 29.41 msec ± 0.3% | 36.70 msec ± 0.6% | 42.46 msec ± 0.7% | 33.07 msec ± 0.8% | 34.31 msec ± 0.4% | 33.08 msec ± 0.5% | 32.92 msec ± 0.3% | 34.09 msec ± 0.9% | 33.88 msec ± 0.6% | 91.45 msec ± 1.0% | 124.9 msec ± 1.7% | 134.3 msec ± 3.9% |
| 3 | 300 | 30 | 0 | 26.09 msec ± 0.6% | 31.05 msec ± 1.0% | 39.24 msec ± 0.8% | 45.48 msec ± 0.9% | 34.91 msec ± 0.6% | 36.62 msec ± 0.9% | 34.89 msec ± 0.9% | 34.73 msec ± 0.8% | 35.90 msec ± 1.2% | 36.02 msec ± 0.7% | 96.39 msec ± 0.4% | 135.1 msec ± 2.4% | 151.3 msec ± 4.0% |
| 4 | 400 | 40 | 0 | 26.76 msec ± 0.8% | 32.17 msec ± 1.1% | 41.02 msec ± 0.9% | 48.06 msec ± 0.8% | 36.33 msec ± 1.4% | 37.88 msec ± 0.8% | 36.72 msec ± 1.2% | 36.08 msec ± 0.9% | 37.47 msec ± 0.5% | 37.39 msec ± 1.2% | 101.4 msec ± 0.7% | 148.8 msec ± 1.8% | 167.6 msec ± 3.0% |
| 6 | 600 | 60 | 0 | 29.38 msec ± 0.5% | 35.87 msec ± 1.3% | 45.83 msec ± 1.0% | 54.15 msec ± 1.1% | 40.61 msec ± 1.0% | 41.98 msec ± 1.2% | 40.92 msec ± 1.5% | 40.55 msec ± 0.9% | 41.11 msec ± 0.8% | 41.83 msec ± 1.2% | 112.5 msec ± 0.6% | 167.4 msec ± 2.2% | 202.9 msec ± 2.4% |
| 8 | 800 | 80 | 0 | 30.97 msec ± 0.9% | 38.30 msec ± 2.1% | 48.81 msec ± 1.1% | 58.61 msec ± 0.7% | 43.28 msec ± 1.7% | 44.59 msec ± 1.2% | 43.15 msec ± 1.3% | 43.08 msec ± 1.1% | 44.29 msec ± 1.5% | 45.07 msec ± 1.7% | 122.9 msec ± 1.4% | 185.3 msec ± 2.0% | 230.7 msec ± 5.7% |
| 12 | 1200 | 120 | 0 | 33.74 msec ± 1.5% | 43.13 msec ± 2.1% | 57.47 msec ± 1.5% | 66.54 msec ± 1.2% | 50.04 msec ± 1.4% | 50.19 msec ± 1.4% | 49.48 msec ± 1.2% | 50.10 msec ± 0.7% | 50.63 msec ± 0.8% | 50.63 msec ± 1.3% | 139.9 msec ± 1.1% | 214.6 msec ± 2.3% | 274.8 msec ± 3.8% |
| 16 | 1600 | 160 | 0 | 37.04 msec ± 2.3% | 47.55 msec ± 2.5% | 64.37 msec ± 1.9% | 75.57 msec ± 2.3% | 55.88 msec ± 1.9% | 57.12 msec ± 1.9% | 55.08 msec ± 2.0% | 55.14 msec ± 0.7% | 55.85 msec ± 1.4% | 55.76 msec ± 1.8% | 158.8 msec ± 0.9% | 248.8 msec ± 2.2% | 331.8 msec ± 5.5% |
| 24 | 2400 | 240 | 0 | 42.25 msec ± 6.2% | 55.01 msec ± 1.1% | 78.58 msec ± 4.2% | 93.01 msec ± 3.5% | 68.31 msec ± 4.1% | 66.26 msec ± 1.5% | 63.91 msec ± 0.3% | 70.01 msec ± 2.9% | 65.83 msec ± 3.3% | 68.35 msec ± 3.6% | 196.9 msec ± 2.1% | 320.9 msec ± 1.9% | 426.8 msec ± 10.4% |
| 32 | 3200 | 320 | 0 | 51.73 msec ± 0.7% | 67.71 msec ± 0.1% | 95.40 msec ± 0.8% | 122.1 msec ± 3.6% | 81.91 msec ± 0.9% | 82.76 msec ± 0.7% | 80.80 msec ± 0.4% | 84.42 msec ± 3.2% | 82.49 msec ± 0.2% | 83.04 msec ± 0.4% | 239.6 msec ± 1.2% | 391.4 msec ± 1.9% | 549.3 msec ± 8.6% |
| 48 | 4800 | 480 | 0 | 72.38 msec ± 0.3% | 95.21 msec ± 0.9% | 136.1 msec ± 0.6% | 178.0 msec ± 2.0% | 116.0 msec ± 2.0% | 117.4 msec ± 0.5% | 114.8 msec ± 1.5% | 124.4 msec ± 1.3% | 122.8 msec ± 3.4% | 117.4 msec ± 0.5% | 332.4 msec ± 1.8% | 588.9 msec ± 2.2% | 831.5 msec ± 5.5% |
| 64 | 6400 | 640 | 0 | 105.4 msec ± 0.9% | 131.2 msec ± 3.0% | 196.8 msec ± 1.7% | 257.4 msec ± 1.5% | 162.0 msec ± 4.1% | 169.4 msec ± 0.6% | 167.7 msec ± 0.1% | 181.0 msec ± 1.7% | 173.2 msec ± 2.8% | 168.5 msec ± 0.7% | 475.9 msec ± 1.1% | 846.8 msec ± 1.0% | 1.122 sec ± 9.0% |
| Geomean: | 37.61 msec ± 1.3% | 46.70 msec ± 1.3% | 62.22 msec ± 1.3% | 74.74 msec ± 1.5% | 54.43 msec ± 1.7% | 55.77 msec ± 1.0% | 54.13 msec ± 0.9% | 55.36 msec ± 1.3% | 55.62 msec ± 1.5% | 55.60 msec ± 1.2% | 153.9 msec ± 1.1% | 235.6 msec ± 2.0% | 291.2 msec ± 5.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.462 ± 2.2% | 0.473 ± 1.3% | 0.471 ± 1.6% | 0.455 ± 2.1% | 0.477 ± 1.2% | 0.477 ± 1.2% | 0.448 ± 2.8% | 0.481 ± 0.9% | 0.478 ± 0.9% | 0.482 ± 0.5% | 0.476 ± 1.2% | 0.480 ± 0.7% | 0.478 ± 0.6% |
| 2 | 200 | 20 | 0 | 1.033 ± 1.3% | 1.065 ± 0.8% | 1.022 ± 1.4% | 1.001 ± 1.2% | 1.050 ± 1.0% | 1.050 ± 1.0% | 1.001 ± 1.5% | 1.089 ± 1.1% | 1.082 ± 1.1% | 1.093 ± 0.8% | 1.102 ± 1.3% | 1.088 ± 0.4% | 1.097 ± 0.7% |
| 3 | 300 | 30 | 0 | 1.432 ± 2.3% | 1.522 ± 1.0% | 1.437 ± 0.9% | 1.401 ± 1.1% | 1.490 ± 0.9% | 1.490 ± 0.9% | 1.411 ± 2.0% | 1.578 ± 0.7% | 1.548 ± 1.3% | 1.558 ± 0.7% | 1.583 ± 0.7% | 1.583 ± 0.3% | 1.585 ± 0.7% |
| 4 | 400 | 40 | 0 | 1.809 ± 0.8% | 1.898 ± 1.1% | 1.812 ± 1.1% | 1.773 ± 1.0% | 1.887 ± 0.7% | 1.887 ± 0.7% | 1.774 ± 1.5% | 2.004 ± 0.3% | 1.969 ± 0.6% | 1.971 ± 0.4% | 2.010 ± 0.4% | 2.012 ± 0.6% | 2.004 ± 0.5% |
| 6 | 600 | 60 | 0 | 2.339 ± 0.7% | 2.482 ± 0.5% | 2.371 ± 0.6% | 2.342 ± 0.7% | 2.447 ± 0.9% | 2.447 ± 0.9% | 2.309 ± 0.5% | 2.654 ± 0.6% | 2.564 ± 1.2% | 2.573 ± 0.6% | 2.654 ± 0.4% | 2.645 ± 0.4% | 2.644 ± 0.6% |
| 8 | 800 | 80 | 0 | 2.818 ± 0.9% | 3.004 ± 0.7% | 2.850 ± 1.0% | 2.810 ± 0.5% | 2.962 ± 0.6% | 2.962 ± 0.6% | 2.807 ± 0.6% | 3.205 ± 0.5% | 3.096 ± 0.4% | 3.091 ± 0.4% | 3.208 ± 0.4% | 3.210 ± 0.5% | 3.206 ± 0.2% |
| 12 | 1200 | 120 | 0 | 3.578 ± 0.5% | 3.825 ± 0.4% | 3.631 ± 0.5% | 3.608 ± 0.6% | 3.766 ± 0.3% | 3.766 ± 0.3% | 3.572 ± 0.5% | 4.111 ± 0.3% | 3.981 ± 0.4% | 3.930 ± 0.4% | 4.133 ± 0.2% | 4.128 ± 0.1% | 4.140 ± 0.2% |
| 16 | 1600 | 160 | 0 | 4.168 ± 0.5% | 4.462 ± 0.5% | 4.246 ± 0.3% | 4.237 ± 0.2% | 4.391 ± 0.5% | 4.391 ± 0.5% | 4.212 ± 0.6% | 4.853 ± 0.2% | 4.651 ± 0.5% | 4.566 ± 0.6% | 4.853 ± 0.3% | 4.871 ± 0.3% | 4.875 ± 0.1% |
| 24 | 2400 | 240 | 0 | 5.214 ± 0.6% | 5.556 ± 0.2% | 5.266 ± 0.3% | 5.341 ± 0.4% | 5.455 ± 0.2% | 5.455 ± 0.2% | 5.263 ± 0.2% | 6.101 ± 0.3% | 5.734 ± 0.5% | 5.582 ± 0.2% | 6.100 ± 0.2% | 6.121 ± 0.1% | 6.138 ± 0.2% |
| 32 | 3200 | 320 | 0 | 5.994 ± 0.3% | 6.418 ± 0.4% | 6.098 ± 0.2% | 6.212 ± 0.3% | 6.299 ± 0.4% | 6.299 ± 0.4% | 6.087 ± 0.5% | 7.102 ± 0.1% | 6.615 ± 0.2% | 6.402 ± 0.5% | 6.987 ± 0.4% | 7.074 ± 0.1% | 7.125 ± 0.2% |
| 48 | 4800 | 480 | 0 | 7.329 ± 0.2% | 7.817 ± 0.1% | 7.442 ± 0.2% | 7.654 ± 0.3% | 7.706 ± 0.2% | 7.706 ± 0.2% | 7.543 ± 0.1% | 8.775 ± 0.1% | 8.074 ± 0.2% | 7.747 ± 0.1% | 8.323 ± 0.4% | 8.464 ± 0.2% | 8.648 ± 0.1% |
| 64 | 6400 | 640 | 0 | 8.573 ± 0.1% | 8.945 ± 0.1% | 8.651 ± 0.1% | 8.899 ± 0.1% | 8.827 ± 0.2% | 8.827 ± 0.2% | 8.752 ± 0.3% | 9.926 ± 0.2% | 9.113 ± 0.2% | 8.877 ± 0.2% | 9.428 ± 0.2% | 9.629 ± 0.0% | 9.798 ± 0.3% |
| Geomean: | 2.806 ± 0.9% | 2.965 ± 0.6% | 2.835 ± 0.7% | 2.824 ± 0.7% | 2.926 ± 0.6% | 2.926 ± 0.6% | 2.799 ± 0.9% | 3.178 ± 0.4% | 3.050 ± 0.6% | 3.016 ± 0.5% | 3.149 ± 0.5% | 3.163 ± 0.3% | 3.177 ± 0.4% |