AccScience Publishing / IJOCTA / Online First / DOI: 10.36922/ijocta.1696
Submit to IJOCTA
Cite this article
5
Download
116
Views
Journal Browser
Volume | Year
Issue
Search
Forthcoming Issue
Current Issue
View All
News and Announcements
View All
RESEARCH ARTICLE

Parallel late acceptance hill-climbing for binary-encoded optimization problems

Emrullah Sonuç1,2* ,  Ender Özcan2
Show Less
1 Department of Computer Engineering, Karabuk University, Türkiye
2 Computational Optimisation and Learning (COL) Lab, School of Computer Science, University of Nottingham, United Kingdom
IJOCTA, 1696 https://doi.org/10.36922/ijocta.1696
Submitted: 30 September 2024 | Accepted: 7 February 2025 | Published: 7 April 2025
© 2025 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
Cite
XML
Abstract

This paper presents a Parallel Late Acceptance Hill-Climbing (PLAHC) algorithm for solving binary-encoded optimization problems, with a focus on the Uncapacitated Facility Location Problem (UFLP) and the Maximum Cut Problem (MCP). The experimental results on various benchmark problem instances demonstrate that PLAHC significantly improves upon the sequential implementation of the standard Late Acceptance Hill-Climbing method in terms of solution quality and computational efficiency. For UFLP instances, an 8-thread implementation with a history list length of 50 achieves the best results, while for MCP instances, a 4-thread implementation with a history list length of 100 is the most effective configuration. The speedup analysis shows performance improvements ranging from 3.33x to 10.00x for UFLP and 2.72x to 9.20x for MCP as the number of threads increases. The performance comparisons to the state-of-the-art algorithms illustrate that PLAHC is highly competitive, often outperforming existing sequential methods, indicating the potential of exploiting parallelism to improve heuristic search algorithms for complex optimization problems.

Keywords
Late acceptance hill-climbing
Max-cut problem
Metaheuristics
Uncapacitated facility location problem
Parallel algorithms
Funding
This study was supported by the Scientific Research Projects Unit of Karabuk University under grant number KBUBAP-24-ABP-047.
Conflict of interest
The authors declare that they have no conflict of interest regarding the publication of this article.
References
  1. Drake JH, Hyde M, Ibrahim K, Ozcan E. A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes. 2014;43(9/10):1500-1511. https://doi.org/10.1108/K-09-2013-0201

 

  1. Sonu¸c E, O¨ zcan E. CUDA-based parallel local search for the set-union knapsack problem. Knowl-Based Syst. 2024;112095. https://doi.org/10.1016/j.knosys.2024.112095

 

  1. Ahmad A, Alzaidi K, Sari M, Uslu H. Prediction of anemia with a particle swarm optimization- based approach. Int J Optim Control Theor Appl. (IJOCTA) 2023;13(2):214-223. https://doi.org/10.11121/ijocta.2023.1269

 

  1. Commander CW. Maximum cut problem, MAX- cut. Encycl Optim. 2009;2. https://doi.org/10.1007/978-0-387-74759-0358

 

  1. Glover F, Hanafi S, Guemri O, Crevits I. A sim- ple multi-wave algorithm for the uncapacitated facility location problem. Front Eng Manag. 2018;5(4):451-465. https://doi.org/10.15302/J-FEM-2018038

 

  1. Talbi EG. Metaheuristics: From Design to Implementation. John Wiley & Sons. 2009. https://doi.org/10.1002/9780470496916

 

  1. Al-Betar MA. β-hill climbing: an exploratory lo- cal search. Neural Comput Appl. 2017;28(Suppl 1):153-168.https://doi.org/10.1007/s00521-016-2328-2

 

  1. Burke EK, Bykov Y. The late acceptance hill-climbing heuristic. Eur J Oper Res. 2017;258(1):70-78. https://doi.org/10.1016/j.ejor.2016.07.012

 

  1. Tari S, Basseur M, Go¨effon A. Expansion-based Hill-climbing. Inf Sci. 2023;649, 119635. https://doi.org/10.1016/j.ins.2023.119635

 

  1. Burke EK, Bykov Y. The late acceptance hill- climbing heuristic. University of Stirling, Tech. Rep. 2012.

 

  1. Alparslan S, Sonu¸c, E.. Solving Static Weapon- Target Assignment Problem using Multi-Start Late Acceptance Hill Climbing. Curr Trends Comput Sci Appl. 2024;2(1):23-35.

 

  1. Bazargani M, Lobo FG. Parameter-less late ac- ceptance hill-climbing. In: Proceedings of the Genetic and Evolutionary Computation Confer- ence. 2017; 219-226. https://doi.org/10.1145/3071178.3071225

 

  1. Goerler A, Schulte F, Voß, S. An application of late acceptance hill-climbing to the traveling purchaser problem. In: Computational Logistics: 4th International Conference ICCL 2013, Copen- hagen, Denmark, September 25-27, 2013. Pro- ceedings 4 2013; 173-183. Springer. https://doi.org/10.1007/978-3-642-41019-213

 

  1. Ghosh M, Kundu T, Ghosh D, Sarkar R. Feature selection for facial emotion recognition using late hill-climbing based memetic algorithm. Multimed Tools Appl. 2019;78, 25753-25779. https://doi.org/10.1007/s11042-019-07811-x

 

  1. Turky A, Sabar NR, Sattar A, Song A. Paral- lel late acceptance hill-climbing algorithm for the google machine reassignment problem. In: AI 2016: Advances in Artificial Intelligence: 29th Australasian Joint Conference Hobart, TAS, Aus- tralia, December 5-8, 2016, Proceedings 29 2016; 163-174. Springer International Publishing. https://doi.org/10.1007/978-3-319-50127-713

 

  1. Clay S, Mousin L, Veerapen N, Jourdan L. Clahc- custom late acceptance hill climbing: First re- sults on tsp. In: Proceedings of the Genetic and Evolutionary Computation Conference Compan- ion. 2021; 1970-1973. https://doi.org/10.1145/3449726.3463129

 

  1. Cao VL, Nicolau M, McDermott J. Late-acceptance and step-counting hill-climbing GP for anomaly detection. In: Proceedings of the Genetic and Evolutionary Computation Conference Com- panion. 2017; 221-222. https://doi.org/10.1145/3067695.3076091

 

  1. Yuan B, Zhang C, Shao X. A late acceptance hill-climbing algorithm for balancing two-sided as- sembly lines with multiple constraints. J Intell Manuf. 2015;26:159-168. https://doi.org/10.1007/s10845-013-0770-x

 

  1. Fonseca GH, Santos HG, Carrano EG. Late ac- ceptance hill-climbing for high school timetabling. J Sched. 2016;19:453-465. https://doi.org/10.1007/s10951-015-0458-5

 

  1. Bolaji AL A, Bamigbola AF, Shola PB. Late acceptance hill climbing algorithm for solving patient admission scheduling problem. Knowl- Based Syst. 2018;145:197-206. https://doi.org/10.1016/j.knosys.2018.01.017

 

  1. Erlenkotter D. A dual-based procedure for uncapacitated facility location. Oper Res. 1978;26(6):992-1009. https://doi.org/10.1287/opre.26.6.992

 

  1. Efroymson M, Ray    A branch-bound algorithm for plant location.  Oper Res. 1966;14(3):361-368. https://doi.org/10.1287/opre.14.3.361

 

  1. Akinc U, Khumawala BM. An efficient branch and bound algorithm for the capacitated warehouse location problem. Manag Sci. 1977;23(6):585-594. https://doi.org/10.1287/mnsc.23.6.585

 

  1. Schrage L. Implicit representation of variable up- per bounds in linear programming. In: Compu- tational practice in mathematical programming. 2009; 118-132. Springer. https://doi.org/10.1007/BFb0120715

 

  1. Galv˜ao RD, Raggi LA. A method for solving to optimality uncapacitated location problems. Ann Oper Res. 1989;18(1):225-244. https://doi.org/10.1007/BF02097805

 

  1. Hoefer M. Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. In: International Workshop on Experimental and Efficient Algorithms. 2003; 165-178. Springer. https://doi.org/10.1007/3-540-44867-513

 

  1. Monabbati E, Kakhki HT. On a class of subaddi- tive duals for the uncapacitated facility location problem. Appl Math 2015;251:118-131. https://doi.org/10.1016/j.amc.2014.10.072

 

  1. Sonu¸c, E.. Binary crow search algorithm for the uncapacitated facility location problem. Neural Comput Appl. 2021;33(21):14669-14685. https://doi.org/10.1007/s00521-021-06107-2

 

  1. Durgut R, Aydin ME. Adaptive binary artifi- cial bee colony algorithm. Appl Soft Comput. 2021;101:107054. https://doi.org/10.1016/j.asoc.2020.107054

 

  1. Sonu¸c, E.,O¨ zcan E. An adaptive parallel evolutionary algorithm for solving the uncapaci- tated facility location problem. Expert Syst Appl. 2023;224:119956. https://doi.org/10.1016/j.eswa.2023.119956

 

  1. Aslan M, Pavone M. MBVS: a modified binary vortex search algorithm for solving uncapacitated facility location problem. Neural Comput Appl. 2024;36(5):2573-2595. https://doi.org/10.1007/s00521-023-09190-9

 

  1. Gao L, Zeng Y, Dong A. An ant colony algo- rithm for solving Max-cut problem. Prog Nat Sci. 2008;18(9):1173-1178. https://doi.org/10.1016/j.pnsc.2008.04.006

 

  1. Festa P, Pardalos PM, Resende MG, Ribeiro CC. Randomized heuristics for the MAX-CUT problem. Optim Methods Softw. 2002;17(6):1033- 1058. https://doi.org/10.1080/1055678021000090033

 

  1. Kim YH, Yoon Y, Geem ZW. A comparison study of harmony search and genetic algorithm for the max-cut problem. Swarm Evol Comput. 2019;44:130-135. https://doi.org/10.1016/j.swevo.2018.01.004

 

  1. Mart´ı, R., Duarte A, Laguna M. Advanced scat- ter search for the max-cut problem. INFORMS J Comput. 2009;21(1):26-38. https://doi.org/10.1287/ijoc.1080.0275

 

  1. Wu Q, Wang Y, Lu¨, Z.. A tabu search based hy- brid evolutionary algorithm for the max-cut prob- lem. Appl Soft Comput. 2015;34:827-837. https://doi.org/10.1016/j.asoc.2015.04.033

 

  1. Kochenberger GA, Hao JK, Lu¨, Z., Wang H, Glover F. Solving large scale max cut problems via tabu search. J Heuristics. 2013;19:565-571. https://doi.org/10.1007/s10732-011-9189-8

 

  1. Akan T, Agahian S, Dehkharghani R. Binbro: Bi- nary battle royale optimizer algorithm. Expert Syst Appl. 2022;195:116599. https://doi.org/10.1016/j.eswa.2022.116599

 

  1. Zhu F, Shuai Z, Lu Y et al. oBABC: A one- dimensional binary artificial bee colony algorithm for binary optimization. Swarm Evol Comput. 2024;87:101567. https://doi.org/10.1016/j.swevo.2024.101567

 

  1. Sˇevi´c, I., Jovanovic R, Uroˇsevi´c, D., Davidovi´c, T. Fixed Set Search Applied to the Max-Cut Problem. In: 2024 IEEE 8th Energy Conference (ENERGYCON). 2024; 1-6. IEEE. https://doi.org/10.1109/ENERGYCON58629.2024. 10488777

 

  1. Beasley JE. OR-Library: distributing test problems by electronic mail. J Oper Res Soc. 1990;41(11):1069-1072. https://doi.org/10.1057/jors.1990.166

 

  1. Wiegele A. Biq Mac Library-A collection of Max- Cut and quadratic 0-1 programming instances of medium size. 2007;51:112-127.
Share
Back to top
An International Journal of Optimization and Control: Theories & Applications, Electronic ISSN: 2146-5703 Print ISSN: 2146-0957, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept