Page 119 - IJOCTA-15-2

¨
E. Sonu¸c, E. Ozcan / IJOCTA, Vol.15, No.2, pp.311-329 (2025)
x ij − y i ≤ 0, i = 1, ..., n, j = 1, ..., m (3) including evolutionary algorithms, scatter search,
x ij ∈ {0, 1}, i = 1, ..., n, j = 1, ..., m (4) and hybrid methods. 32 Randomized heuristics like
y i ∈ {0, 1}, i = 1, ..., n. (5) GRASP and VNS were proposed yielding near-
optimal solutions. 33 Another metaheuristic algo-
rithm was proposed to compare the performance
In the Eq. 1, c ij represents the cost of servic- against traditional genetic algorithms. 34 An ad-
vanced scatter search and a tabu search based
ing demand from facility i for customer j, while f i 35
denotes the fixed cost associated with opening a hybrid evolutionary algorithm 36 have showed
facility at location i. The objective of the UFLP competitive performance in solving MCP. A
is to minimize the total cost, which comprises tabu search algorithm was presented to effec-
both service costs and facility opening costs, as tively solve large-scale MCPs. 37 Recent focus has
represented by the first and second terms in Eq. shifted to adapting continuous optimization al-
(1), respectively. Constraint (2) states that each gorithms for discrete problems, introducing the
customer must be served by exactly one facility. binary evolutionary algorithm (BinBRO) 38 and
Constraint (3) ensures that customers cannot re- a one-dimensional binary evolutionary algorithm
ceive service from a facility that is not opera- (oBABC). 39 Another study is proposed a novel
tional. Constraints (4) and (5) define the binary optimization algorithm called fixed set search for
nature of the decision variables, restricting them solving MCP, demonstrating effectiveness over
to values of either 0 or 1. GRASP by incorporating a learning procedure. 40
Exact algorithms for UFLP developed since These studies demonstrate the ongoing evolution
the 1960s include branch-and-bound, 22 improved of optimization approaches for MCP, with hybrid
linear programming methods, 23,24 and hybrid methods and binary adaptations showing promise
approaches. 25 However, these methods often re- for future research.
quire large amounts of memory or computational
time, which limits their applicability to small- 3. The proposed parallel late
scale problems. 26 Exact solvers struggle with acceptance hill-climbing
larger instances of 100-500 facilities. 27 As a result,
metaheuristics have become preferred due to their To address the limitations of the LAHC algo-
ability to efficiently find near-optimal solutions in rithm, such as the computational time required
larger UFLP instances. 28–31 to reach an optimal solution by iteratively search-
ing with a single solution, the algorithm can be
2.2.2. Maximum cut problem split into independent tasks suitable for concur-
rent execution. Task splitting identifies oppor-
The Maximum Cut Problem (MCP) is a max- tunities for parallelism, such as evaluating can-
imization BEOP in graph theory and combina- didate solutions and updating the solution his-
torial optimization. An undirected graph G =
tory. The implementation of the parallel LAHC
(V, E), where V is the set of vertices and E is
algorithm involves the use of a multi-threaded
the set of edges. The aim is that partition V into
approach, where multiple threads simultaneously
two subsets S and T (V − S) such that the total
execute different instances of the LAHC. Threads
weight (or number) of edges with one endpoint in can be used to efficiently manage concurrency and
S and the other in T is maximized. The problem resource allocation. Multiple instances of LAHC
can be encoded as a binary-encoding where each can be run simultaneously, allowing for a larger
bit represents a vertex. A ‘0’ might indicate the exploration and exploitation of potential solutions
vertex is in set S, while a ‘1’ indicates it’s in set in different regions of the search space. The pro-
T (or vice versa). The mathematical formulation posed Parallel LAHC (PLAHC) is shown in Fig-
of MCP is as follows: ure 2. According to the figure, PLAHC initially
reads the problem instance from a file. Then,
X
maximize w(u, v) · [x u ̸= x v ] (6) the number of threads to execute the LAHC algo-
(u,v)∈E rithm in parallel is set. Here, the history list can
be a list that can be used by all threads (shared),
where x u and x v represent the binary values as- or it can be a separate list for each thread (local).
signed to nodes u and v in Eq. 6, respectively. In our study, each thread maintains its own his-
If x u ̸= x v , then these two nodes are in different tory list (local). Following these steps, the spec-
sets and the edge is cut. ified number of threads (nt) are created, and the
MCP has been addressed by various heuristic parallel section is initiated using OpenMP. In this
and metaheuristic approaches. Recent literature section, each thread executes its own LAHC algo-
reveals a diverse range of optimization techniques, rithm. First, each thread starts by generating a
314