Benchmark Results - Problem C4 - 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 | 3 | 25.53 msec ± 0.4% | 30.89 msec ± 0.3% | 38.79 msec ± 0.4% | 45.54 msec ± 0.1% | 34.99 msec ± 0.3% | 35.56 msec ± 0.6% | 35.25 msec ± 0.6% | 34.91 msec ± 0.4% | 36.04 msec ± 0.6% | 35.82 msec ± 0.5% | 95.96 msec ± 0.8% | 128.9 msec ± 1.5% | 136.9 msec ± 2.5% |
| 2 | 300 | 20 | 6 | 27.41 msec ± 0.6% | 34.29 msec ± 0.9% | 43.77 msec ± 0.7% | 52.03 msec ± 0.5% | 39.09 msec ± 0.7% | 39.36 msec ± 0.7% | 39.01 msec ± 0.5% | 38.91 msec ± 0.4% | 40.05 msec ± 1.0% | 39.84 msec ± 0.6% | 105.6 msec ± 1.1% | 148.0 msec ± 1.0% | 163.9 msec ± 3.3% |
| 3 | 450 | 30 | 9 | 28.61 msec ± 1.0% | 36.73 msec ± 1.1% | 48.15 msec ± 1.0% | 57.83 msec ± 0.5% | 42.57 msec ± 0.4% | 42.60 msec ± 0.5% | 42.86 msec ± 0.8% | 42.23 msec ± 0.7% | 43.79 msec ± 0.8% | 43.28 msec ± 0.6% | 112.9 msec ± 0.7% | 162.8 msec ± 1.8% | 181.1 msec ± 2.7% |
| 4 | 600 | 40 | 12 | 30.94 msec ± 1.0% | 40.49 msec ± 0.7% | 53.96 msec ± 0.7% | 65.83 msec ± 0.6% | 47.95 msec ± 1.2% | 46.44 msec ± 0.9% | 47.44 msec ± 1.0% | 47.19 msec ± 0.9% | 48.34 msec ± 0.7% | 48.31 msec ± 0.6% | 124.3 msec ± 0.7% | 183.3 msec ± 1.8% | 217.2 msec ± 5.9% |
| 6 | 900 | 60 | 18 | 33.29 msec ± 1.3% | 46.49 msec ± 1.1% | 64.35 msec ± 0.7% | 80.83 msec ± 0.7% | 55.39 msec ± 1.1% | 53.45 msec ± 1.2% | 55.10 msec ± 0.6% | 55.79 msec ± 0.9% | 56.94 msec ± 1.0% | 56.23 msec ± 0.6% | 141.9 msec ± 1.0% | 213.6 msec ± 1.2% | 246.6 msec ± 5.3% |
| 8 | 1200 | 80 | 24 | 35.48 msec ± 1.7% | 52.49 msec ± 0.9% | 76.33 msec ± 1.2% | 96.34 msec ± 1.0% | 64.40 msec ± 0.9% | 60.87 msec ± 1.2% | 63.78 msec ± 0.9% | 64.19 msec ± 1.0% | 64.82 msec ± 0.7% | 65.65 msec ± 0.9% | 158.8 msec ± 0.9% | 246.6 msec ± 2.6% | 296.9 msec ± 3.3% |
| 12 | 1800 | 120 | 36 | 40.08 msec ± 3.1% | 64.79 msec ± 2.3% | 101.5 msec ± 1.1% | 131.6 msec ± 0.4% | 83.97 msec ± 1.9% | 77.96 msec ± 1.4% | 81.80 msec ± 1.3% | 87.56 msec ± 1.5% | 84.87 msec ± 1.0% | 85.79 msec ± 0.7% | 197.6 msec ± 0.9% | 307.6 msec ± 2.4% | 397.2 msec ± 5.1% |
| 16 | 2400 | 160 | 48 | 44.12 msec ± 0.7% | 80.78 msec ± 0.7% | 129.7 msec ± 0.4% | 174.3 msec ± 0.9% | 104.6 msec ± 1.3% | 95.79 msec ± 1.1% | 104.0 msec ± 1.2% | 113.0 msec ± 1.7% | 105.8 msec ± 0.9% | 107.7 msec ± 0.9% | 239.1 msec ± 1.2% | 379.1 msec ± 1.8% | 472.3 msec ± 4.3% |
| 24 | 3600 | 240 | 72 | 57.31 msec ± 0.5% | 121.8 msec ± 0.6% | 204.3 msec ± 0.5% | 289.8 msec ± 2.8% | 166.5 msec ± 1.3% | 153.7 msec ± 2.2% | 158.6 msec ± 1.6% | 180.3 msec ± 1.1% | 166.1 msec ± 1.8% | 166.6 msec ± 0.8% | 341.5 msec ± 0.5% | 558.9 msec ± 1.8% | 670.1 msec ± 1.8% |
| 32 | 4800 | 320 | 96 | 72.73 msec ± 0.8% | 178.7 msec ± 1.3% | 308.3 msec ± 0.8% | 428.3 msec ± 1.1% | 247.3 msec ± 3.0% | 238.0 msec ± 2.4% | 239.4 msec ± 2.7% | 276.1 msec ± 2.5% | 250.7 msec ± 1.9% | 251.6 msec ± 2.9% | 485.9 msec ± 1.6% | 777.6 msec ± 2.2% | 972.9 msec ± 6.1% |
| 48 | 7200 | 480 | 144 | 108.7 msec ± 1.1% | 342.7 msec ± 0.8% | 618.3 msec ± 3.2% | 887.2 msec ± 0.5% | 486.6 msec ± 0.6% | 444.5 msec ± 0.5% | 486.4 msec ± 1.9% | 521.5 msec ± 2.7% | 491.6 msec ± 1.3% | 483.2 msec ± 2.4% | 863.3 msec ± 1.6% | 1.453 sec ± 4.4% | 1.775 sec ± 3.9% |
| 64 | 9600 | 640 | 192 | 139.4 msec ± 0.5% | 698.7 msec ± 8.8% | 1.414 sec ± 0.9% | 2.089 sec ± 6.1% | 1.098 sec ± 4.2% | 870.6 msec ± 3.3% | 1.011 sec ± 2.0% | 1.255 sec ± 3.1% | 1.071 sec ± 3.9% | 1.178 sec ± 2.6% | 1.781 sec ± 4.0% | 3.157 sec ± 3.2% | 4.914 sec ± 5.1% |
| Geomean: | 45.64 msec ± 1.1% | 82.87 msec ± 1.6% | 125.8 msec ± 1.0% | 163.7 msec ± 1.3% | 105.6 msec ± 1.4% | 99.60 msec ± 1.3% | 103.8 msec ± 1.3% | 110.0 msec ± 1.4% | 106.9 msec ± 1.3% | 107.7 msec ± 1.2% | 241.1 msec ± 1.2% | 371.7 msec ± 2.1% | 449.9 msec ± 4.1% |
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 | 3 | 0.431 ± 3.6% | 0.450 ± 1.2% | 0.440 ± 2.5% | 0.421 ± 1.4% | 0.451 ± 0.7% | 0.438 ± 2.7% | 0.431 ± 3.0% | 0.450 ± 0.7% | 0.451 ± 1.9% | 0.458 ± 0.4% | 0.456 ± 0.5% | 0.457 ± 0.7% | 0.457 ± 0.5% |
| 2 | 300 | 20 | 6 | 0.791 ± 2.6% | 0.909 ± 1.6% | 0.823 ± 2.7% | 0.786 ± 1.5% | 0.874 ± 3.0% | 0.867 ± 2.8% | 0.815 ± 3.2% | 0.932 ± 1.7% | 0.874 ± 3.1% | 0.892 ± 2.1% | 0.952 ± 1.5% | 0.962 ± 1.5% | 0.964 ± 2.3% |
| 3 | 450 | 30 | 9 | 1.065 ± 4.1% | 1.253 ± 2.6% | 1.169 ± 1.7% | 1.123 ± 1.3% | 1.230 ± 1.7% | 1.185 ± 1.7% | 1.174 ± 0.9% | 1.266 ± 2.0% | 1.249 ± 1.9% | 1.250 ± 1.4% | 1.333 ± 1.0% | 1.336 ± 0.8% | 1.332 ± 1.0% |
| 4 | 600 | 40 | 12 | 1.277 ± 2.8% | 1.533 ± 2.0% | 1.428 ± 1.4% | 1.415 ± 2.3% | 1.496 ± 1.3% | 1.451 ± 1.3% | 1.435 ± 1.8% | 1.497 ± 2.5% | 1.557 ± 1.5% | 1.482 ± 2.0% | 1.659 ± 1.2% | 1.664 ± 0.7% | 1.668 ± 1.2% |
| 6 | 900 | 60 | 18 | 1.636 ± 1.7% | 2.055 ± 1.6% | 1.941 ± 0.7% | 1.907 ± 1.4% | 2.010 ± 0.9% | 1.932 ± 1.3% | 1.929 ± 0.8% | 2.050 ± 1.4% | 2.074 ± 1.6% | 2.050 ± 0.9% | 2.191 ± 0.9% | 2.208 ± 1.3% | 2.229 ± 0.7% |
| 8 | 1200 | 80 | 24 | 1.959 ± 1.6% | 2.495 ± 1.0% | 2.395 ± 1.2% | 2.318 ± 0.9% | 2.454 ± 0.8% | 2.335 ± 1.0% | 2.372 ± 1.3% | 2.511 ± 1.9% | 2.518 ± 1.2% | 2.469 ± 0.7% | 2.617 ± 0.6% | 2.654 ± 0.9% | 2.664 ± 1.0% |
| 12 | 1800 | 120 | 36 | 2.495 ± 1.1% | 3.193 ± 0.9% | 3.061 ± 0.5% | 2.958 ± 0.9% | 3.170 ± 0.9% | 3.039 ± 0.8% | 3.078 ± 1.7% | 3.184 ± 1.1% | 3.178 ± 0.9% | 3.160 ± 1.2% | 3.310 ± 0.7% | 3.324 ± 1.3% | 3.332 ± 0.6% |
| 16 | 2400 | 160 | 48 | 3.075 ± 0.9% | 3.821 ± 0.2% | 3.598 ± 1.0% | 3.444 ± 0.9% | 3.751 ± 0.7% | 3.639 ± 0.4% | 3.650 ± 0.8% | 3.841 ± 0.8% | 3.831 ± 1.4% | 3.770 ± 0.7% | 3.882 ± 0.5% | 3.897 ± 0.4% | 3.948 ± 0.4% |
| 24 | 3600 | 240 | 72 | 4.099 ± 0.8% | 4.694 ± 0.2% | 4.391 ± 1.1% | 4.302 ± 0.5% | 4.629 ± 0.5% | 4.548 ± 0.4% | 4.564 ± 0.4% | 4.710 ± 0.6% | 4.661 ± 0.8% | 4.633 ± 0.4% | 4.713 ± 0.9% | 4.704 ± 0.6% | 4.732 ± 0.7% |
| 32 | 4800 | 320 | 96 | 5.016 ± 0.4% | 5.501 ± 0.2% | 5.193 ± 0.5% | 5.138 ± 0.3% | 5.431 ± 0.4% | 5.491 ± 0.6% | 5.374 ± 0.9% | 5.542 ± 0.4% | 5.396 ± 1.0% | 5.429 ± 0.6% | 5.502 ± 0.9% | 5.487 ± 0.4% | 5.503 ± 0.9% |
| 48 | 7200 | 480 | 144 | 6.507 ± 0.1% | 6.794 ± 0.2% | 6.805 ± 0.2% | 6.817 ± 0.2% | 6.819 ± 0.5% | 6.985 ± 0.1% | 6.786 ± 0.2% | 6.930 ± 0.2% | 6.823 ± 0.2% | 6.882 ± 0.2% | 6.843 ± 0.3% | 6.833 ± 0.1% | 6.835 ± 0.2% |
| 64 | 9600 | 640 | 192 | 7.862 ± 0.2% | 8.263 ± 0.1% | 8.308 ± 0.2% | 8.298 ± 0.1% | 8.293 ± 0.1% | 8.302 ± 0.1% | 8.240 ± 0.1% | 8.360 ± 0.1% | 8.313 ± 0.0% | 8.293 ± 0.1% | 8.327 ± 0.1% | 8.315 ± 0.1% | 8.323 ± 0.2% |
| Geomean: | 2.187 ± 1.6% | 2.537 ± 1.0% | 2.418 ± 1.1% | 2.358 ± 1.0% | 2.503 ± 0.9% | 2.452 ± 1.1% | 2.427 ± 1.3% | 2.550 ± 1.1% | 2.532 ± 1.3% | 2.520 ± 0.9% | 2.620 ± 0.8% | 2.628 ± 0.7% | 2.637 ± 0.8% |
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 | 3 | 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 | 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% |
| 3 | 450 | 30 | 9 | 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 | 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% |
| 6 | 900 | 60 | 18 | 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 | 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% |
| 12 | 1800 | 120 | 36 | 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 | 48 | 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 | 72 | 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% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% |
| 32 | 4800 | 320 | 96 | 0.986 ± 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 | 144 | 0.976 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 0.992 ± 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% |
| 64 | 9600 | 640 | 192 | 0.967 ± 0.1% | 0.998 ± 0.0% | 0.998 ± 0.0% | 0.999 ± 0.0% | 0.998 ± 0.0% | 0.977 ± 0.1% | 0.997 ± 0.0% | 0.997 ± 0.0% | 0.998 ± 0.0% | 0.998 ± 0.0% | 0.999 ± 0.0% | 0.999 ± 0.0% | 0.999 ± 0.0% |
| Mean: | 0.994 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 1.000 ± 0.0% | 0.997 ± 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% |