Page 132 - IJOCTA-15-2

Parallel late acceptance hill-climbing for binary-encoded optimization problems
Our experimental results demonstrate that hybrid strategies. By extending the experimen-
PLAHC significantly improves upon the sequen- tal setup to a wider range of problem instances
tial LAHC implementation in terms of solution and configurations, future research can provide
quality and computational efficiency. For UFLP deeper insights into the performance of PLAHC
instances, the 8-thread parallel implementation under diverse and challenging conditions, thereby
with a history list length (L) of 50 emerged as addressing the scalability concerns raised in this
the best overall configuration, achieving the low- study.
est average gap score of 0.29. For MCP instances,
the 4-thread parallel implementation with an L Acknowledgments
of 100 consistently achieved the best results. Per- None.
formance comparisons with state-of-the-art algo-
rithms show that PLAHC is highly competitive, Funding
often outperforming existing methods.
This study was supported by the Scientific Re-
Despite these results, our extensive testing search Projects Unit of Karabuk University under
pointed out several important limitations of the grant number KBUBAP-24-ABP-047.
algorithm and its parallel implementation. While
significant speedups were achieved, ranging from Conflict of interest
3.33x to 10.00x for UFLP and from 2.72x to 9.20x
The authors declare that they have no conflict of
for MCP, the performance improvements exhibit
interest regarding the publication of this article.
sub-linear scaling as the number of threads in-
creases. This indicates diminishing returns due Author contributions
to communication overhead and algorithmic parts
that cannot be perfectly parallelized. Further- Conceptualization: All authors
more, for larger problem instances, especially Formal analysis: Emrullah Sonu¸c
when combined with high degrees of parallelism, Investigation: All authors
very long history lists can lead to suboptimal ex- Methodology: Emrullah Sonu¸c
¨
ploration of the solution space, suggesting a com- Supervision: Ender Ozcan
plex interaction between parallelism and search Visualization: Emrullah Sonu¸c
history that requires fine tuning. Writing – original draft: Emrullah Sonu¸c
¨
Writing – review & editing: Ender Ozcan
The experimental results revealed additional
challenges related to thread interference effects Availability of data
and problem instance scaling. Excessive paral- Not applicable.
lelism, especially when combined with longer his-
tory lists, can lead to over-exploration or thread References
interference. This effect was observed for problem
1. Drake JH, Hyde M, Ibrahim K, Ozcan E.
instances with extreme configurations, where per-
A genetic programming hyper-heuristic for the
formance degraded as the number of threads in-
multidimensional knapsack problem. Kybernetes.
creased. In addition, the scalability of PLAHC al-
2014;43(9/10):1500-1511.
gorithm for larger problem sizes remains an open
https://doi.org/10.1108/K-09-2013-0201
area for further study. For example, while the cur- 2. Sonu¸c E, Ozcan E. CUDA-based parallel lo-
¨
rent study focused on benchmark sets with well- cal search for the set-union knapsack problem.
defined sizes and computational budgets, future Knowl-Based Syst. 2024;112095.
research could extend these experiments to larger https://doi.org/10.1016/j.knosys.2024.112095
problem instances (e.g., UFLP with more diverse 3. Ahmad A, Alzaidi K, Sari M, Uslu H. Prediction
customer and facility sizes, or MCP with larger of anemia with a particle swarm optimization-
graph configurations) to better assess the scala- based approach. Int J Optim Control Theor Appl.
bility and robustness of the algorithm. (IJOCTA) 2023;13(2):214-223.
https://doi.org/10.11121/ijocta.2023.1269
The relationship between the number of 4. Commander CW. Maximum cut problem, MAX-
threads and performance improvement is non- cut. Encycl Optim. 2009;2.
linear, indicating that further refinement of the https://doi.org/10.1007/978-0-387-74759-0 3 58
parallel implementation is needed. This could in- 5. Glover F, Hanafi S, Guemri O, Crevits I. A sim-
clude exploring adaptive mechanisms for dynam- ple multi-wave algorithm for the uncapacitated
ically adjusting the length of history lists, im- facility location problem. Front Eng Manag.
2018;5(4):451-465.
proving thread coordination, or using alternative
https://doi.org/10.15302/J-FEM-2018038
parallelization frameworks (e.g., MPI, CUDA) or
327