A Weighted-Based Fast Local Search for α-Neighbor p-Center Problem

1 Introduction

The p-center problem is a well-known problem in the field of combinatorial optimization, which has been proven to be NP-hard [Kariv and Hakimi, 1979]. It involves finding p centers in a given set of candidate centers, such that the maximum distance from any demand client to its nearest center is minimized. The p-center problem has a wide range of applications, such as the problems of determining the locations of emergency centers [Toregas et al., 1971], hospitals [Hakimi, 1964], and fire stations [Drezner, 1987] to serve the communities. In the last 50 years, the p-center problem has been wide studied in academic society. There are mainly three kinds of methodologies, including exact algorithms [Minieka, 1970; Ilhan et al., 2002; Elloumi et al., 2004; Calik and Tansel, 2013; Liu et al., 2020], approximation algorithms [Hochbaum and Shmoys, 1985; Martinich, 1988], and metaheuristic algorithms [Mladenovi´c et al., 2003; Pullan, 2008; Irawan et al., 2016; Yin et al., 2017; Zhang et al., 2020].

∗Corresponding Author

However, a center may be forced to close due to an unpredictable incident, such as natural disasters, sudden system failures. In this case, the clients served by the reference center have to turn to other backup centers as quickly as possible. This issue has been classified into two cases based on whether the client can obtain information about center faults in advance. In the first case, the client cannot know the fault information and must first arrive at the closest center and then to the next one. This scenario is described as the p-next center problem [Albareda-Sambola et al., 2015; Zhang et al., 2022]. In the second case, the client can know the fault information in advance. At this time, the client can directly move to the nearest available backup center, which is the α-neighbor p-center problem (α-pCP) that this paper focuses on studying. With the increasing convenience of information sharing, the importance of the α-pCP is growing.

Krumke [1995] first introduced the α-pCP, which occurs in many industrial applications and has been proven to be NPhard [Kariv and Hakimi, 1979]. Its aim is to locate p centers from a set of candidate centers and assign up to α centers to each client, such that the maximum distance of each client to its assigned centers is minimized. The closest center serves as the primary reference center, while the second to the αth nearest centers act as backup centers. For the α-pCP, the given vertices not only are the clients but also the candidate centers. Figure 1 shows an illustrative diagram of the α-pCP, where Figure 1(a) is the original graph and Figure 1(b) is a solution of p = 3, α = 2.

In previous years, the study of the α-pCP focused on the theoretical study of approximation algorithms. Krumke [1995] introduced different formulations for α-pCP

4. Khuller et al. [2000] presented two approximation algorithms. The first achieves an approximation factor of 3 for any α, and the second with an approximation factor of 2 for α < 4. Based on [Krumke, 1995] and [Khuller et al., 2000], L´opez-S´anchez et al. [2019] proposed a 2-approximation algorithm to further improve the quality of the solution.

In addition to theoretical studies, some practical studies of exact and heuristic algorithms have been introduced in recent years. S´anchez-Oro et al. [2022a] introduced a metaheuristic algorithm, which combines a greedy randomized adaptive search procedure with tabu search, and a strategic oscillation (SO) post-processing procedure to ensure high solution quality to the α-pCP. Cura [2023] proposed a competitive algorithm that combines the mayfly optimization algorithm (MA) with a local search procedure for the α-pCP. Gaar and Sinn [2023] presented two integer programming formulations and developed a branch-and-cut algorithms for the α-pCP. To the best of our knowledge, it is the most recent and best performing method currently to solve the α-pCP.

In this paper, we present a weighting-based fast local search (WFLS) algorithm to solve the α-pCP. Unlike previous metaheuristics that directly optimize the original problem, WFLS transforms the original α-pCP into a series of decision subproblems by specifying a serving radius. These subproblems are then efficiently solved using a weighting-based fast local search procedure that adopts a swap-based neighborhood structure and an incremental neighborhood evaluation technique based on a refined-grained penalty strategy.

The main contributions of our work are as follows:

• We propose a novel approach that transforms the αneighbor p-center optimization problem into a series of decision subproblems, introducing a new decisionbased MIP model. We obtain the solution to the original problem by sequentially solving these subproblems. It smooths the solution space and prevents gradient vanishing, enhancing the effectiveness of local search-based algorithms to solve the α-pCP.
• We introduce a weighting technique for local search, resulting in an effective search procedure called weighting-based fast local search (WFLS), which increases search diversity and allows the algorithm to escape from the local optimal trap.
• WFLS algorithm employs a new neighborhood structure based on a dedicated swap move comprising a closing operation and an opening operation. In addition, we use a new refined-grained penalty strategy for neighborhood evaluation, two scoring functions to guide the neighboring search, and an incremental evaluation strategy to improve the efficiency of the search.
• Tested on 154 classical instances of the α-pCP, WFLS algorithm improves the best known results for 69 instances and matches on all the remaining ones in the

literature, respectively. In addition, the computational time of WFLS is much shorter than that of the state-ofthe-art algorithms in the literature.

2 ProblemDescription and Transformation

Given an undirected complete graph G = (V, E), where V = {1, 2, ..., n} is the vertex set and E = {(i, j)|i, j ∈ V } is the edge set. dij denotes the distance between each pair of vertices i and j. The α-pCP aims to select a center subset C (|C| = p) from the set V to minimize the maximum distance between each client i ∈ (V \ C) and its α serving centers.

Based on the above notations, the classical mixed-integer programming (MIP) model [Gaar and Sinnl, 2023] for the αpCP can be formulated as follows.

x and y are decision variables, where xj = 1 iff a candidate center j ∈ V is opened, yij = 1 iff client i ∈ V is served by candidate center j, and r ∈ R+ denotes the upper bound of the serving radius. Objective (1) is intended to minimize the service radius. Constraint (2) restricts the number of opened centers to be no more than p. Constraints (3) ensure that each vertex is either assigned to exactly α centers or opened to be a center. Constraints (4) restrict that only those centers that are in an open state can serve the client vertices. Constraints (5) ensure that the radius r is not less than the length of any arc from each client to its all α serving centers.

Obviously, to obtain the optimal serving radius, there is at least one equality in Constraints (5), i.e., the optimal serving radius of a specific α-neighbor p-center instance must be the same as the length of a certain edge dij . Let R = {dij |i, j ∈ V } = {r1, r2, . . . , rm} be the ordered list containing all distinct values of dij , where r1 < r2 < ... < rm. The α-pCP is to find the rank q of the smallest radius on R such that the model is still feasible after adding a constraint r ≤ rq, but it becomes infeasible if we add constraint r ≤ rq-1.

Problem Transformation. Based on the above analysis, the α-pCP can be solved by finding feasible solutions to a series of subproblems with the given radius. Specifically, it is transformed into decision subproblems where serving arcs are bounded by r, and centers need to be located under the constraint that the actual radius does not exceed r. Therefore, the focus is limited to center-client pairs with distances not exceeding the current radius r. In detail, we employ a vertex set Sq j = {i ∈ V |dij ≤ rq, i ̸= j} to represent the set of clients that candidate center j ∈ V can serve within covering radius rq, or the set of candidate centers that can serve the

Algorithm 1 The main framework of the WFLS algorithm

Input A graph G, the center number p, the value of α Output The best solution found so far X∗

• 1: iter ← 1, vertex weights wi ← 1, ∀i ∈ V
• 2: The age aj ← 0, ∀j ∈ V
• 3: Current solution X, initial radius rq ← Initialize(G, p)
• 4: Previous solution X′ ←X, X∗ ←X
• 5: The radius order list R = {r1, r2, ..., rq}
• 6: while Termination condition is not met do
• 7: q ← q -1, update the set of illegal vertices I(X)
• 8: while The time limit is not reached and |I(X)| > 0 do
• 9: (i, j) ← find the best swap move /* Algorithm 2 */
• 10: X ←X ∪ {i} \ {j}
• 11: if |I(X)| = 0 then
• 12: X∗ ← X

13:

else if (|I(X)| > |I(X′ )| then

• 15: end if
• 16: X′ ←X, iter ← iter +1
• 17: end while
• 18: end while
• 19: return X∗

client j. Therefore, with the optimal edge length rank q specified, the new reformulated model (α-pCPq) can be defined by Eqs. (8)-(11), where ui is a binary variable that equals 1 if client i is not covered by at least α centers, and xj is the same decision variable as in the model (α-pCP).

Model (α-pCPq) minimizes the number of uncovered vertices by exactly opening p centers as shown in objective function (8). Constraints (9) ensure that for each vertex, there are at least α centers within the covering radius rq or it is opened to be a center. We need to traverse the distinct edge length list R to examine each possible covering radius.

3 VertexWeighting-Based Local Search

3.1 General Framework

To address the α-pCP, we transform it into a series of decision subproblems for a given radius and solve these subproblems using the weighting-based fast local search (WFLS). Firstly, it adopts a greedy constructive heuristic algorithm to obtain an initial feasible solution and the upper bound of the radius. Subsequently, WFLS converts α-pCP into a series of rq-radius α-pCP decision subproblems and solves them by a fast local search procedure combining with a weighting technique. As soon as the rq-radius α-pCP is solved, we decrease rq by setting rq to rq-1 and solve the resulting subproblem once again. In practical applications, these subproblems can actually be solved in parallel.

Specifically, Algorithm 1 outlines the main framework of WFLS. It starts by generating an initial solution X with an initial radius rq using a greedy construction algorithm under the principle of minimizing the objective (1) (line 3). Using the initial radius rq, we initialize the ordered radius list R with all distance lengths (line 5). Then, the model (α-pCPq) is solved by decreasing q to q - 1 in turn until it fails to find any feasible solution for model (α-pCPq-1) within the given time limit. For each subproblem, we record the set of client vertices that are not fully covered by α centers, and define it as the illegal vertices set I(X). This set is iteratively optimized by fast local search until |I(X)| = 0 or the time limit is reached (lines 8-17).

3.2 Reduction Rule

To simplify the original graph and reduce the scale of the search space, we develop a reduction rule to simplify the graph. Specifically, we fix some centers that must be included in the optimal solution. Since each vertex can be both a client and a center, if there exists vertex k whose number of candidate centers that can cover it within the given radius is less than α, i.e., |Sk| < α, then vertex k must be a center in order to find a feasible solution.

3.3 Reformulation andWeighting Technique

The weighting technique helps the search to escape from local optimum by introducing an adaptive objective function. The weighting strategy has been successfully applied to many problems, such as the single-cost set cover problem [Gao et al., 2015], the classical p-center problem [Zhang et al., 2020], and the optimal camera placement problem [Su et al., 2021]. We transform the α-pCP into a series of decision subproblems to determine whether all client vertices can be assigned to α centers within a specific r-radius. To effectively solve each subproblem, the constraint requiring each vertex to be assigned to α centers within the radius r or opened to be a center is relaxed, and a penalty is imposed for each illegal vertex in the objective function.

Specifically, let wi be the weight of vertex i, the objective function f(X) can be defined as Eq. (12), which is the sum of the weights of each illegal vertex.

The initial weight assigned to each vertex is set to 1. During subsequent searches, if WFLS fails to reduce the number of illegal vertices, it indicates that the search is trapped in a local optimum. To address this issue, WFLS increases the weight wk of each illegal vertex k ∈ I(X) ⊂ V by one unit when the search falls into local optimum (Algorithm 1, lines 13-15).

In the later stage of the search, once stagnation is encountered, the weight of the corresponding illegal vertices is increased, and the more times a vertex appears in I(X), the greater its weight will be. The weighting strategy changes

Algorithm 2 Find the best swap move

Input Current solution X, the set of illegal vertices I(X), the number of iteration iter, the age a of candidate centers Output The best swap move (i∗ , j ∗ )

• 1: Best swap move (i∗ , j ∗ ) ←∅, ∆f ∗ 1 ←+∞
• 2: k ←a random vertex in I(X)
• 3: for all i ∈ Sk \X ∪ {k} do
• 4: Virtually update Scorej, {j ∈ Sv ∩ X|v ∈ Si, cv = α + 1}, which affects the calculation of ∆f1(i, j)
• 5: for all j ∈ X do
• 6: j is not the recently-opened center
• 7: if (∆f1(i, j) < ∆f ∗ 1 ) or ((∆f1(i, j) = ∆f ∗ 1 ) ∩ (ai > a∗i )) then
• 8: ∆f ∗ 1 ← ∆f1(i, j), (i∗ , j ∗ ) ← (i, j)
• 9: end if
• 10: end for
• 11: end for
• 12: Return (i∗ , j ∗ )

the landscape of the solution space, thus effectively preventing vertices from remaining illegal for following periods.

3.4 Neighborhood Structure and Evaluation

The neighborhood structure defines the set of solutions adjacent to a given solution in the solution space. For the current solution X, a neighborhood move move generates a new solution X ⊕ move. To tackle each rq-radius α-pCP subproblem, WFLS adopts a swap-based neighborhood structure. Specifically, a swap move consists of opening a center i ∈ V \ X and closing a center j ∈ X, denoted as move(i, j). At each iteration, based on the incumbent solution X, WFLS tries to improve X by selecting the bestimprovement move to produce a new neighborhood solution X ⊕ move(i, j) = X ∪ {i} \ {j}.

The neighborhood evaluation is an essential and the most time-consuming part of trajectory-based metaheuristic algorithms. To improve the incumbent solution X and optimize the objective value, the local search procedure follows a bestimprovement policy, evaluating all neighborhood moves and selecting the one that leads to the best neighboring solution. Evaluating a neighborhood move involves calculating the weighted sum of illegal vertices, as specified by Eq. (12). If the weighted sum is naively calculated, the time complexity is O(p · (n - p)). Since there are totally O(p · (n - p)) neighborhood moves, the neighborhood evaluation complexity of a round of local search is O((p · (n - p))2 ), making the process quite time-consuming, especially for large scale instances. To enhance efficiency without sacrificing the solution quality, WFLS adopts three acceleration and guiding strategies, which include a refined-grained penalty strategy for neighborhood evaluation, an incremental evaluation technique, and two scoring functions.

Refined-grained penalty strategy. WFLS uses a refinedgrained penalty strategy to reformulate the neighborhood evaluation function, providing a more nuanced evaluation approach. Instead of classifying the client status directly as legal or illegal, we assign penalties to illegal clients based on the number of centers currently covering them. The more centers there are that can cover a client, the easier it is to be fully covered by α centers, and thus the smaller the penalty factor will be. Conversely, fewer covering centers result in a larger penalty factor. To capture this distinction, we use varying penalty factors for illegal vertices. Specifically, the distance to legal covering is used as the penalty factor, i.e., α - ck. The new neighborhood evaluation function is presented in Eq. (13),

where ck denotes the number of centers currently covering client k, i.e., ck = |Sk ∩X|. This penalty strategy provides a finer-grained neighborhood evaluation and prioritizes the full covering of more difficult illegal clients, leading to improved solutions by directing the search more efficiently.

Incremental evaluation technique. To accelerate the neighborhood evaluation procedure, WFLS adopts an incremental evaluation mechanism to efficiently evaluate neighborhood moves instead of naively calculating the reformulated objective by Eq. (13). Specifically, since there are only small changes from the current solution to a neighboring solution, the objective of a neighboring solution can be calculated incrementally by the variation of closing a center i and opening a center j, i.e., f(X ⊕move(i, j)) = f(X) +∆f(i, j), where ∆f represents the increment of the objective value after performing a swap move. WFLS uses Score to record the (potential) contribution of each (candidate) center to the current solution, enabling rapid incremental evaluation of the objective value based on Score. Score is defined and calculated according to Eq. (14).

For an opening center j ∈ X, Scorej is the sum of the weights of clients that j can cover, which is either not fully covered or exactly covered by α centers, i.e., ck ≤ α; For a closing center j /∈ X, Scorej is the sum of the weights of nofully covered clients that j can cover. When ck > α, center j does not contribute to the current client k that can be covered, as closing it leaves k still legally covered. It is worth noting that since the vertices are both convertible between the center and the client, the calculation of the contribution values needs to take themselves into account. To facilitate the calculation of Score, we categorize the clients into three states, ck < α, ck = α, and ck > α. According to the definition of Score, its value needs to be updated only when the state of the client changes. Obviously, opening a center i causes clients with ck = α - 1 to transfer to ck = α, and clients with ck = α to transfer to ck > α. Conversely, closing a center j causes clients with ck = α + 1 to transfer to ck = α, and clients with ck = α to transfer to ck < α. Thus, when trying to open i and close j, the increment of the neighborhood move is calculated as Eq. (15).

Two scoring functions. During neighborhood evaluation, using only the objective function often results in multiple best neighboring solutions. To address this issue, WFLS employs two scoring functions. The primary scoring function minimizes the refined-grained weighted sum of illegal vertices, as this aligns with the redefined optimization objective as defined in Eq. (13). To further distinguish multiple best swap moves with the same primary score and effectively mitigate the gradient vanishing issue, WFLS uses a secondary scoring function. The age ai of center i refers to the number of iterations since it has been last closed. For two solutions having the same weighted sum of illegal vertices, preferring the opening of older candidate centers helps the search to explore new configurations and enhances the search diversification, which is usually more promising to improve the current solution. Therefore, WFLS introduces the age as the secondary scoring function. Specifically, for a move move(i, j) producing a neighboring solution X, it is calculated as follows:

where i∗ denotes the open center of the best swap move (i∗ , j ∗ ). At each iteration, WFLS selects the best swap move with the smallest ∆f1 value, and breaks ties by choosing the move with the largest ∆f2 value.

In addition, to prevent immediately re-closing the recentlyopened center, the recently-opened center will not be evaluated and selected at the next iteration.

Algorithm 2 presents the neighborhood evaluation procedure for the α-pCP, where each vertex can be legalized as either a client (requiring α assigned centers) or as a center. Our WFLS considers both these two cases in the neighborhood evaluation (line 3).

3.5 Neighborhood Reduction

To accelerate the neighborhood search, WFLS proposes one neighborhood reduction strategy.

WFLS restricts to choose the candidate centers by focusing on a single illegal client at a time. As we know, the objective value can only be improved by covering the vertices in I(X) or opening them as centers, so WFLS evaluates a swap move move(i, j) only if i ∈ I(X) or can cover some vertices in I(X). For the rq-radius α-pCP subproblem, since each client must be eventually fully covered by at least α centers, WFLS randomly selects a vertex k ∈ I(X), and evaluates only neighborhood moves move(i, j) where i ∈ Sk and j ∈ X. The approach significantly reduces the neighborhood size from O(p · (n-p)) to O(p · |Sk|), with the side effect of enhancing the search diversification.

4 Experiments and Analysis

To evaluate the performance of WFLS, we conduct extensive experiments on 154 public benchmark instances and compare WFLS with the state-of-the-art algorithms in the literature, such as SO [S´anchez-Oro et al., 2022b], MA [Cura, 2023], and 1HSVL and 2HVSL [Gaar and Sinnl, 2023].

4.1 Experimental Benchmarks and Protocol

There are 154 instances with α = 2, 3 for the α-pCP generated from TSP-Library [Reinelt, 1991]. The vertex number n varies from 48 to 1323, and the center number p ranges from 10 to 140. In these instances, location is given in twodimensional coordinates, and distances between any two vertices i, j are calculated using the Euclidean metric.

Our WFLS is coded in C++ and all our experiments are carried out on Windows Server 2019 x64 with an Intel Xeon Gold 6133 2.50GHz CPU. For each instance, we carried out 20 independent runs under 180 seconds time limit. The computational platform for the reference algorithms 1HSVL and 2HVSL is an Intel Xeon E5-2670v2 machine with 2.5GHz and 6GB of RAM, and the time limit for each instance is 1800 seconds. The reference algorithms MA and SO are tested on an Apple M2 Pro 12-core 3480 MHz computer with 16GB RAM running MacOS Ventura and the time limit is 1800 seconds. Compared to the reference algorithms, the maximum runtime of our algorithm is reduced by a factor of 10. Moreover, our algorithm has converged within this time limit, and extending the running time has almost no impact on the results. It shows the high efficiency of our algorithm. Notably, there are no parameters that need to be tuned in our WFLS.

4.2 Computational Results

To test the performance of WFLS, we report the detailed performance metrics and results in Tables 1 and 2.

"Instances with α = 2 (77)" and "Instances with α = 3 (77)" represent the group of instances whose neighbor α = 2 and α = 3, respectively, with a total of 77 instances in each group. Column Instance gives the instance names. Columns n and p report the numbers of vertices and centers, respectively. Column Gap indicates the average gap between the results obtained by the corresponding algorithm and the best results on the current set of instances. Column CPU shows the average CPU execution time in seconds. For our WFLS, the CPU time includes the total time for computing the initial solution and solving all the decisions. Column UB represents the best upper bound obtained by these algorithms, and the numbers in bold stand for the best known results. Column #best shows the number of instances where the corresponding algorithms match the best known results. Columns #B, #E, and #W indicate the number of instances where our WFLS obtains better, equal, and worse results compared to the corresponding algorithms, respectively. To verify the statistical significance of the comparison between WFLS and the reference algorithms, we give the p-values by the non-parametric Wilcoxon test in column p-value, where a p-value less than

0.05 indicates a significant difference In addition, based on model (α-pCPq), we find the optimal objective value for some instances using the Gurobi 11.0.3 solver with 1800 seconds time limit per instance, which matches the time limit used in the 1HSVL/2HVSL exact algorithm. The proven optimal objective values are marked with '*'.

Table 1 summarizes the overall results on all the instances obtained by SO, MA, 1HSVL, 2HVSL, and our WFLS and Gurobi (α-pCPq). It is evident that WFLS achieves the best known results on all the 154 instances (Gap = 0). Specifically, compared to the best-performing algorithm 2HVSL, WFLS obtains 35 better, 42 equal, and no worse solutions for

"α = 2" group, and 31 better, 46 equal and no worse solutions for "α = 3" group. The maximum p-value is much less than 0.05, further indicating the superiority of WFLS in terms of the quality of solution. Moreover, WFLS has the shortest average CPU time, with 16.98 (20.11) seconds for α = 2 (3), while the average CPU times of all the reference algorithms exceed 500 seconds. It shows that WFLS outperforms all reference algorithms in terms of both solution quality and computational efficiency across all instances.

Table 2 summarizes detailed experimental results for improved instances and large-scale challenging instances with more than 500 vertices, comparing our algorithm with the top performers (MA, 1HSVL, and 2HVSL) 1 . From Table 2, we can observe that the proposed WFLS improves the previous best known results and outperforms all reference algorithms on these large instances in terms of computing time. For the remaining 68 instances, WFLS matches the optimal or the best known solutions. On large instances, the average gap between the best results obtained by WFLS and the best results found by all the algorithms (including ours) is 0, while for other competitors, the average gap is larger than 5%. It is important to note that even a 1% gap is considered to be significant due to the large value of UB for large graphs. Furthermore, compared to the best 1HSVL and 2HVSL exact algorithms, our model (α-pCPq) can prove the optimality for 11 more instances and find better upper bounds for the remaining ones. In summary, these statistics indicate that WFLS is highly effective and efficient to solve the α-pCP.

4.3 Analysis and Discussion

To evaluate the effectiveness of the weighting technique, the incremental evaluation technique, the two scoring functions, and the refined-grained penalty strategy for neighborhood evaluation, we compare WFLS with four alternative versions.

1 The complete results are available in https://github.com/Zhangqingyun/alphaPCP-WFLS.

• WFLSNW: Evaluate neighborhood evaluation in the naive way.
• WFLSf2 : Disable the secondary scoring function, using a random strategy to break ties.
• WFLSw: Deactivate the weighting technique.
• WFLSRP: Disable the refined-grained penalty strategy, i.e., the objective function uses Eq. (12).

We conduct experiments on large instances with vertex numbers greater than 500 with α = 2, 3. These versions have the same settings as WFLS. Table 3 presents the comparison of each alternative version with WFLS. Columns UB and CPU give the average best upper bound and CPU time for these versions on the corresponding set of instances.

From Table 3, one can observe that WFLS outperforms the other four variants. Specifically, WFLS obtains better results on nearly all the 80 tested instances. The average CPU execution time and the best upper bound of WFLS are significantly better than other four variants.

To further compare each variant, Figure 2 gives the trend of the objective value on four representative instances (rl1323 with p = 40, 100, and α = 2, 3). Each point (x, y) on the curve represents a gap of y between the objective value of the current solution and the best known solution at the x microsecond. We can observe that WFLS obtains the best known solutions for all these instances with faster convergence, while other versions fail to do so.

These observations indicate that the proposed strategies are essential to the effectiveness and efficiency of WFLS.

5 Conclusion

In this paper, we study a variant of the p-center problem, referred to as α-neighbor p-center problem (α-pCP), and propose a weighting-based fast local search (WFLS) algorithm to solve this challenging NP-hard problem. The original optimization problem is decomposed into a series of decision subproblems for a given radius, which are then solved sequentially. Tested on 154 commonly used benchmark instances and compared with several state-of-the-art algorithms in the literature, our WFLS improves the previous best known results on 69 instances, while matching the best records in the literature for all the remaining ones in much shorter time. This demonstrates that WFLS is highly competitive in terms of both effectiveness and efficiency for solving the α-pCP.

Acknowledgments

We are grateful to the anonymous reviewers for their helpful comments. This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 62402191, and 62202192, the Special Project for Knowledge Innovation of Hubei Province under Grant 2022013301015175, and Interdiciplinary Research Program of Hust 5003300129