Page 128 - IJOCTA-15-2

Parallel late acceptance hill-climbing for binary-encoded optimization problems
Table 11. Gap scores for MCP instances with different number of threads on PLAHC where L = 100

Instance 4 thds 8 thds 16 thds 32 thds
pw01 100.0 0.7098 1.2566 2.3789 3.7593
pw01 100.1 0.5714 0.9772 1.9888 3.1359
pw01 100.2 0.8022 1.0566 1.7879 2.6068
pw01 100.3 0.8016 1.2274 2.6352 4.3493
pw01 100.4 0.8176 1.7474 3.4036 4.4679
pw01 100.5 0.7936 1.7566 2.9331 4.3819
pw01 100.6 0.8253 1.6845 2.8430 4.3356
pw01 100.7 0.4725 1.0882 1.8963 3.3558
pw01 100.8 0.9545 1.6864 2.7829 4.3917
pw01 100.9 0.6050 0.9362 1.9636 3.5112
pw05 100.0 0.2487 0.5137 0.6972 0.9955
pw05 100.1 0.3198 0.5158 0.6865 1.2098
pw05 100.2 0.2347 0.4756 0.6838 0.9084
pw05 100.3 0.3231 0.6594 1.0718 1.6673
pw05 100.4 0.2511 0.4107 0.6810 1.1434
pw05 100.5 0.3774 0.5211 0.9907 1.4355
pw05 100.6 0.2300 0.4710 0.6730 1.0941
pw05 100.7 0.1197 0.3342 0.6756 1.1472
pw05 100.8 0.1699 0.4744 1.0940 1.4786
pw05 100.9 0.1840 0.5948 0.9647 1.3487
pw09 100.0 0.2088 0.3185 0.4750 0.7499
pw09 100.1 0.1824 0.3421 0.4418 0.6266
pw09 100.2 0.2704 0.4601 0.5839 0.6777
pw09 100.3 0.2631 0.4674 0.6175 0.8577
pw09 100.4 0.1663 0.3732 0.6608 0.7868
pw09 100.5 0.1537 0.2399 0.4165 0.5413
pw09 100.6 0.3556 0.4646 0.6820 0.8908
pw09 100.7 0.2150 0.3538 0.4269 0.6229
pw09 100.8 0.1727 0.2906 0.4995 0.7708
pw09 100.9 0.2077 0.3776 0.5482 0.8471
Avg.Gap 0.4003 0.7359 1.2728 1.9365

12.00 11.01

9.00
Speedup 6.00 4.78 6.12

2.93
3.00

0.00
4 8 16 32
Number of Threads

Figure 4. Comparison between sequential and parallel implementation of LAHC in terms of average speedup
for MCP instances

the execution times of both sequential and par- to 0.02-0.08 seconds. Medium-sized in-
allel LAHC implementations across all problem stances (50×50) show moderate computa-
instances. Tables 13 and 14 show the average tion times of 0.22-0.35 seconds for sequen-
execution times in seconds for UFLP and MCP tial execution. The most major computa-
instances, respectively. tional demands are observed in the large in-
For UFLP instances, the execution times stances (100×1000), where sequential execu-
show a clear correlation with problem dimen- tion times reach 7.06-7.38 seconds, highlight-
sions. Small instances (16×50 and 25×50) ing the increased complexity of these problem
are solved rapidly, with sequential LAHC sizes.
requiring only 0.12-0.24 seconds and par- The MCP instances show a clear pattern with
allel implementations further reducing this respect to graph density. Problems with lower
323