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

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.