Benchmark Results - Problem C3 - Optimization Strategies
Tested Optimization strategies (1000 iterations):
name |
class |
params |
Constraint-aware |
|---|---|---|---|
RS |
OptimRandomSwaps | False | |
GS(1) |
OptimGuidedSwaps | min_swap_size=1 max_swap_size=1 |
True |
GS(2) |
OptimGuidedSwaps | min_swap_size=2 max_swap_size=2 |
True |
GS(3) |
OptimGuidedSwaps | min_swap_size=3 max_swap_size=3 |
True |
GS(1-3) |
OptimGuidedSwaps | min_swap_size=1 max_swap_size=3 |
True |
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) |
True |
GS(1-3,wide) |
OptimGuidedSwaps | min_swap_size=1 max_swap_size=3 remove_selectivity_modifier=-0.8 add_selectivity_modifier=-0.8 |
True |
GS(1-3,narrow) |
OptimGuidedSwaps | min_swap_size=1 max_swap_size=3 remove_selectivity_modifier=0.8 add_selectivity_modifier=0.8 |
True |
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) |
True |
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) |
True |
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 |
True |
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 |
True |
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 |
True |
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 | 150 | 10 | 2 | 25.68 msec ± 0.5% | 31.04 msec ± 0.4% | 38.70 msec ± 0.3% | 45.46 msec ± 0.3% | 34.99 msec ± 0.5% | 35.40 msec ± 0.5% | 35.17 msec ± 0.7% | 34.93 msec ± 0.8% | 35.83 msec ± 0.4% | 35.81 msec ± 0.4% | 95.14 msec ± 0.7% | 125.3 msec ± 2.1% | 131.7 msec ± 1.2% |
| 2 | 300 | 20 | 4 | 27.20 msec ± 0.3% | 34.14 msec ± 0.5% | 43.23 msec ± 0.9% | 51.33 msec ± 0.5% | 38.76 msec ± 0.5% | 38.97 msec ± 0.4% | 38.77 msec ± 0.6% | 37.97 msec ± 0.5% | 39.47 msec ± 0.6% | 39.54 msec ± 0.8% | 104.8 msec ± 1.0% | 145.0 msec ± 2.1% | 158.6 msec ± 2.7% |
| 3 | 450 | 30 | 6 | 28.44 msec ± 0.3% | 36.28 msec ± 0.9% | 46.69 msec ± 1.1% | 56.25 msec ± 0.6% | 41.81 msec ± 0.4% | 41.96 msec ± 1.0% | 41.58 msec ± 0.7% | 40.68 msec ± 0.5% | 42.67 msec ± 0.6% | 42.30 msec ± 0.8% | 112.1 msec ± 0.5% | 159.9 msec ± 1.3% | 180.0 msec ± 2.0% |
| 4 | 600 | 40 | 8 | 30.29 msec ± 0.5% | 39.90 msec ± 1.0% | 52.07 msec ± 0.9% | 63.06 msec ± 0.7% | 46.31 msec ± 0.4% | 45.32 msec ± 0.8% | 46.30 msec ± 0.7% | 45.34 msec ± 1.0% | 46.78 msec ± 0.8% | 47.18 msec ± 0.4% | 122.1 msec ± 1.0% | 180.5 msec ± 1.6% | 213.6 msec ± 4.4% |
| 6 | 900 | 60 | 12 | 32.95 msec ± 1.7% | 44.58 msec ± 1.2% | 60.91 msec ± 1.1% | 74.48 msec ± 0.4% | 52.51 msec ± 0.9% | 51.31 msec ± 1.1% | 52.58 msec ± 1.2% | 53.36 msec ± 0.9% | 53.49 msec ± 1.0% | 54.12 msec ± 1.0% | 139.8 msec ± 0.8% | 214.9 msec ± 1.9% | 250.0 msec ± 2.5% |
| 8 | 1200 | 80 | 16 | 35.49 msec ± 1.9% | 51.05 msec ± 1.4% | 70.68 msec ± 0.7% | 87.41 msec ± 0.8% | 60.51 msec ± 1.0% | 56.59 msec ± 1.1% | 59.73 msec ± 1.4% | 59.79 msec ± 0.4% | 60.43 msec ± 1.0% | 61.83 msec ± 1.4% | 156.3 msec ± 1.0% | 243.9 msec ± 3.0% | 292.6 msec ± 5.9% |
| 12 | 1800 | 120 | 24 | 39.40 msec ± 2.6% | 63.17 msec ± 2.1% | 88.77 msec ± 1.6% | 115.7 msec ± 1.5% | 77.20 msec ± 1.7% | 68.08 msec ± 1.0% | 75.85 msec ± 1.9% | 76.21 msec ± 1.0% | 77.26 msec ± 1.9% | 77.91 msec ± 1.5% | 191.3 msec ± 1.4% | 312.6 msec ± 2.5% | 388.5 msec ± 6.2% |
| 16 | 2400 | 160 | 32 | 43.80 msec ± 0.7% | 72.98 msec ± 0.5% | 111.5 msec ± 2.8% | 143.5 msec ± 0.8% | 91.68 msec ± 1.0% | 81.47 msec ± 0.9% | 90.31 msec ± 0.9% | 95.36 msec ± 1.2% | 92.23 msec ± 1.4% | 93.89 msec ± 0.8% | 225.4 msec ± 1.4% | 386.1 msec ± 2.6% | 487.3 msec ± 7.1% |
| 24 | 3600 | 240 | 48 | 57.78 msec ± 0.9% | 107.9 msec ± 0.9% | 167.8 msec ± 3.1% | 227.7 msec ± 1.6% | 138.9 msec ± 1.5% | 119.2 msec ± 1.4% | 136.9 msec ± 2.8% | 146.7 msec ± 2.0% | 138.2 msec ± 0.7% | 140.8 msec ± 0.8% | 327.7 msec ± 1.4% | 558.5 msec ± 2.2% | 743.4 msec ± 2.5% |
| 32 | 4800 | 320 | 64 | 73.85 msec ± 1.4% | 150.6 msec ± 1.6% | 250.8 msec ± 1.6% | 347.8 msec ± 2.4% | 204.2 msec ± 1.4% | 168.3 msec ± 2.4% | 197.4 msec ± 1.6% | 218.9 msec ± 1.0% | 204.2 msec ± 1.6% | 207.3 msec ± 0.9% | 440.7 msec ± 1.0% | 781.8 msec ± 2.0% | 1.128 sec ± 8.3% |
| 48 | 7200 | 480 | 96 | 118.3 msec ± 3.0% | 265.6 msec ± 1.0% | 460.1 msec ± 0.2% | 642.5 msec ± 0.5% | 362.3 msec ± 1.2% | 304.1 msec ± 1.2% | 360.6 msec ± 1.0% | 400.9 msec ± 1.1% | 386.7 msec ± 0.4% | 358.6 msec ± 0.5% | 751.4 msec ± 1.2% | 1.358 sec ± 2.0% | 1.881 sec ± 6.1% |
| 64 | 9600 | 640 | 128 | 143.0 msec ± 2.3% | 515.2 msec ± 5.3% | 816.3 msec ± 2.2% | 1.096 sec ± 8.2% | 662.6 msec ± 6.2% | 530.0 msec ± 2.4% | 767.3 msec ± 1.7% | 792.4 msec ± 5.7% | 637.9 msec ± 3.6% | 628.7 msec ± 5.0% | 1.255 sec ± 2.1% | 2.482 sec ± 2.8% | 3.320 sec ± 3.4% |
| Geomean: | 45.91 msec ± 1.3% | 75.76 msec ± 1.4% | 108.8 msec ± 1.4% | 138.5 msec ± 1.5% | 92.69 msec ± 1.4% | 84.71 msec ± 1.2% | 93.07 msec ± 1.3% | 95.54 msec ± 1.3% | 93.61 msec ± 1.2% | 93.65 msec ± 1.2% | 225.7 msec ± 1.1% | 360.9 msec ± 2.2% | 443.7 msec ± 4.4% |
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 | 150 | 10 | 2 | 0.530 ± 1.0% | 0.541 ± 1.2% | 0.534 ± 0.9% | 0.518 ± 1.2% | 0.538 ± 0.6% | 0.538 ± 0.7% | 0.531 ± 1.1% | 0.542 ± 1.5% | 0.541 ± 0.3% | 0.537 ± 1.7% | 0.542 ± 0.6% | 0.544 ± 0.7% | 0.542 ± 0.6% |
| 2 | 300 | 20 | 4 | 1.070 ± 2.3% | 1.163 ± 1.3% | 1.102 ± 1.3% | 1.072 ± 2.4% | 1.150 ± 0.7% | 1.158 ± 1.5% | 1.067 ± 1.1% | 1.176 ± 1.5% | 1.174 ± 0.6% | 1.167 ± 1.2% | 1.182 ± 0.6% | 1.188 ± 0.6% | 1.190 ± 0.8% |
| 3 | 450 | 30 | 6 | 1.398 ± 2.0% | 1.580 ± 1.0% | 1.513 ± 1.1% | 1.465 ± 2.3% | 1.562 ± 1.0% | 1.557 ± 2.0% | 1.456 ± 1.9% | 1.637 ± 1.1% | 1.618 ± 1.4% | 1.625 ± 1.1% | 1.650 ± 1.0% | 1.660 ± 0.6% | 1.660 ± 0.6% |
| 4 | 600 | 40 | 8 | 1.661 ± 3.5% | 1.972 ± 1.2% | 1.870 ± 1.4% | 1.841 ± 1.7% | 1.939 ± 1.4% | 1.928 ± 1.4% | 1.797 ± 2.0% | 2.085 ± 0.8% | 2.041 ± 0.5% | 2.044 ± 1.2% | 2.099 ± 0.8% | 2.106 ± 0.5% | 2.097 ± 0.4% |
| 6 | 900 | 60 | 12 | 2.146 ± 1.4% | 2.560 ± 0.7% | 2.478 ± 1.1% | 2.384 ± 0.7% | 2.507 ± 0.9% | 2.505 ± 1.3% | 2.367 ± 0.8% | 2.767 ± 0.4% | 2.671 ± 0.7% | 2.714 ± 0.8% | 2.775 ± 0.4% | 2.771 ± 0.5% | 2.781 ± 0.4% |
| 8 | 1200 | 80 | 16 | 2.397 ± 3.8% | 3.069 ± 0.5% | 2.982 ± 1.0% | 2.899 ± 0.6% | 3.028 ± 0.5% | 2.981 ± 0.7% | 2.873 ± 1.3% | 3.305 ± 0.4% | 3.195 ± 0.3% | 3.206 ± 0.6% | 3.308 ± 0.5% | 3.322 ± 0.6% | 3.312 ± 0.4% |
| 12 | 1800 | 120 | 24 | 2.776 ± 3.1% | 3.849 ± 0.5% | 3.741 ± 0.4% | 3.704 ± 0.4% | 3.828 ± 0.5% | 3.712 ± 1.2% | 3.608 ± 0.9% | 4.171 ± 0.4% | 4.019 ± 0.3% | 4.031 ± 0.4% | 4.163 ± 0.4% | 4.193 ± 0.4% | 4.184 ± 0.4% |
| 16 | 2400 | 160 | 32 | 3.283 ± 2.2% | 4.523 ± 0.5% | 4.432 ± 0.4% | 4.372 ± 0.3% | 4.500 ± 0.3% | 4.394 ± 0.6% | 4.268 ± 0.5% | 4.874 ± 0.2% | 4.716 ± 0.6% | 4.701 ± 0.5% | 4.881 ± 0.3% | 4.893 ± 0.3% | 4.897 ± 0.4% |
| 24 | 3600 | 240 | 48 | 4.246 ± 0.6% | 5.559 ± 0.2% | 5.439 ± 0.3% | 5.393 ± 0.6% | 5.497 ± 0.2% | 5.361 ± 0.5% | 5.247 ± 0.5% | 5.895 ± 0.3% | 5.704 ± 0.8% | 5.630 ± 0.5% | 5.888 ± 0.2% | 5.944 ± 0.6% | 5.964 ± 0.3% |
| 32 | 4800 | 320 | 64 | 5.274 ± 0.2% | 6.330 ± 0.5% | 6.247 ± 0.3% | 6.216 ± 0.3% | 6.371 ± 0.4% | 6.220 ± 0.2% | 6.081 ± 0.2% | 6.697 ± 0.3% | 6.535 ± 0.3% | 6.377 ± 0.1% | 6.616 ± 0.1% | 6.749 ± 0.3% | 6.768 ± 0.4% |
| 48 | 7200 | 480 | 96 | 6.741 ± 0.1% | 7.590 ± 0.6% | 7.495 ± 0.2% | 7.354 ± 0.7% | 7.556 ± 0.5% | 7.585 ± 0.3% | 7.284 ± 0.2% | 8.037 ± 0.3% | 7.736 ± 0.5% | 7.561 ± 0.5% | 7.907 ± 0.4% | 7.988 ± 0.5% | 8.102 ± 0.2% |
| 64 | 9600 | 640 | 128 | 8.070 ± 0.2% | 8.695 ± 0.2% | 8.620 ± 0.1% | 8.548 ± 0.4% | 8.684 ± 0.4% | 8.791 ± 0.3% | 8.546 ± 0.2% | 9.060 ± 0.3% | 8.805 ± 0.5% | 8.664 ± 0.1% | 8.894 ± 0.2% | 8.990 ± 0.4% | 9.030 ± 0.2% |
| Geomean: | 2.549 ± 1.7% | 3.040 ± 0.7% | 2.958 ± 0.7% | 2.900 ± 1.0% | 3.014 ± 0.6% | 2.988 ± 0.9% | 2.867 ± 0.9% | 3.202 ± 0.6% | 3.123 ± 0.6% | 3.107 ± 0.7% | 3.196 ± 0.5% | 3.217 ± 0.5% | 3.222 ± 0.4% |
Constraint 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 | 150 | 10 | 2 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 2 | 300 | 20 | 4 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 3 | 450 | 30 | 6 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 4 | 600 | 40 | 8 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 6 | 900 | 60 | 12 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 8 | 1200 | 80 | 16 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 12 | 1800 | 120 | 24 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 16 | 2400 | 160 | 32 | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 24 | 3600 | 240 | 48 | 0.999 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 32 | 4800 | 320 | 64 | 0.989 ± 0.1% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 48 | 7200 | 480 | 96 | 0.965 ± 0.1% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 64 | 9600 | 640 | 128 | 0.951 ± 0.1% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 0.997 ± 0.1% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| Mean: | 0.992 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |