A Swap Relaxation-Based Local Search for the Latin Square Completion Problem

1 Introduction

Let n be a positive integer. A Latin square of order n is an n × n grid of cells in which each cell is filled with a symbol from 1 to n so that each symbol appears exactly once in each row and each column. One can be given a n×n grid in which some cells are already filled with a symbol but other cells are empty. The Latin Square Completion (LSC) problem of order n consists in filling each empty cell with a symbol to form a Latin square.

The LSC problem was first introduced by Hall [1948] and Ryser [1951]. Besides its theoretical significance as a canonical NP-complete problem [Colbourn, 1984], the LSC problem has wide applications in various domains, ranging from optical networks [Barry and Humblet, 1993], scheduling [Kumar et al., 1999], error correcting codes [Colbourn et al.,

∗Co-corresponding author.

2004], as well as combinatorial design [Lov´asz et al., 2003; Colbourne and Dinitz, 2007], etc.

As a challenging combinatorial problem, the LSC has attracted a lot of attention from academic society in recent decades. Among them there are several exact algorithms: Gomes and Shmoys [2002] proposed three complete solution approaches for solving the LSC problem by encoding the problem into constraint satisfaction (CSP) formulation, hybrid linear programming/CSP formulation and boolean satisfibility (SAT) formulation. In addition, Ans´otegui et al. [2004] performed a systematic comparison of SAT and CSP models for the LSC problem.

Apart from exact algorithms, several metaheuristic algorithms have been proposed for solving the LSC problem to obtain high-quality solutions for large scale instances within reasonable time. Haraguchi [2016] presented four effective iterated local search algorithms with different neighborhoods. Jin and Hao [2019] proposed a population-based memetic algorithm called MMCOL for solving the LSC problem by transforming the n × n grid of cells to a domain-constrained Latin square graph. Pan et al. [2022] proposed a fast local search algorithm called FastLSC which is based on a reduction reasoning technique, a novel conflict value selection heuristic as well as a history information perturbation mechanism, after modelling the LSC problem as a graph coloring problem. To the best of our knowledge, FastLSC significantly outperforms other metaheuristic algorithms. However, there are still rooms for improvement in terms of the success rate on very hard instances.

In this paper, we also consider the LSC problem as a graph coloring problem, but directly solve it by utilizing its specific features. Specifically, we propose a swap relaxation-based local search (SRLS) algorithm, which incorporates a new search space definition, a swap relaxation-based neighborhood, two scoring functions and an adaptive restart mechanism. One of the key features of SRLS is that its search space is significantly smaller than that of MMCOL and FastLSC.

Our main contributions can be summarized as follows:

1. We propose two novel reduction rules to reduce the color domains, which can dominate the previous ones.
2. We introduce a new search space definition which imposes that each symbol appears exactly once in each row, and then this restricted search space allows us to define a

• swap-based neighborhood which exchanges the symbols of two cells on the same row and always keeps conflictfree on each row.
• By introducing a color domain relaxation technique, we expand the search space of the swap-based neighborhood such that the search can easily connect high-quality solutions via the solutions with color domain violations. Besides, two effective scoring functions are employed to select a neighboring solution with immediate and potential impacts, which can simultaneously optimize the number of conflicting edges as well as the number of color domain violations.
• We present a mechanism to restart the local search from the best found solution when the current solution quality is relatively poor. In addition, the threshold of judging whether the solution quality is relatively poor is adaptively updated as the local search proceeds, which balances the exploitation and exploration of the search.
• Tested on 1819 public benchmark instances widely used in the literature, the proposed SRLS outperforms the state-of-the-art algorithms on all the tested instances in terms of both success rate and computational efficiency.
• We conduct an ablation study to justify the merits of the key components of our SRLS algorithm, including the color domain relaxation technique, the secondary scoring function and the adaptive restart mechanism.

2 Preliminaries

A partial Latin square Lp of order n can be associated with a so-called Latin square graph G = (V,E) [Jin and Hao, 2019], where V = {vij | 1 ≤ i ≤ n, 1 ≤ j ≤ n} is the set of all cells and vij denotes the cell on the ith row and the jth column, and E denotes the edge set where (u, v) ∈ E iff cells u and v are on the same row or column. Clearly, |V | = n2 and |E| = n2 (n - 1), because there are n(n-1)/2 edges for each row or each column. The set of the cells on the kth row is denoted as RVk = {vkj | 1 ≤ j ≤ n} and the set of the cells on the kth column is denoted as CVk = {vik | 1 ≤ i ≤ n}.

The LSC problem is essentially a graph coloring problem on the associated Latin square graph G = (V,E) defined above, with the symbols in Latin square being considered as the colors for G. Let D(v) denote the color domain of cell v in the graph. If cell v is filled with symbol k (1 ≤ k ≤ n), the color domain D(v) is a single-value domain {k}, while the (initial) color domain of each unfilled cell u is D(u) = {1, . . . , n}. The LSC problem is then to find a color mapping C : V → {1, . . . , n} such that for all v ∈ V , C (v) ∈ D (v) and for each (u, v) ∈ E, C (v) ̸= C (u), which is a special case of the precoloring extension problem [Bir´o et al., 1992].

For any (u, v) ∈ E, if C (u) = C (v), u and v are called conflicting cells and (u, v) is called a conflicting edge. The set of conflicting edges of solution C is represented as CE (C). The quality of the solution is evaluated by |CE (C) |. For a conflicting edge (u, v), if u and v are on the same row, (u, v) is called a row conflict. Otherwise, (u, v) is called a column conflict. For the situation where a cell v is colored with the color not in its color domain, i.e., C (v) /∈ D(v), it is called a color domain violation. DV (C) denotes the set of the cells which lead to color domain violations of solution C.

Based on the above notations, the LSC problem after relaxation can be formulated as follows:

Objective (1) aims to minimize the number of conflicting edges. Obviously, a feasible solution of the original LSC problem must be the optimal solution of this model, i.e., |CE (C) | = 0. Constraint (2) stipulates that the color of each cell must be selected from its color domain. Thus, the LSC problem is transformed from a constraint satisfaction problem to an optimization problem.

3 Swap Relaxation-Based Local Search

A Latin square is an n-coloring without any row conflict or column conflict. Therefore, if we always keep the solution without row conflicts, and change the solution only by swapping the colors of two cells on the same row, the LSC problem is simplified to only eliminating the column conflicts, so that the search space is greatly restricted.

In this study, we propose a swap relaxation-based local search algorithm called SRLS for the LSC problem, by adopting the restricted search space, which is quite different from the previous one which changes the color of one cell to another color at each iteration to eliminate both row and column conflicts. Next, we will first present the main framework of SRLS, and then describe its key components.

3.1 Main Framework

The main framework of the proposed SRLS algorithm is presented in Algorithm 1. A distinguishing feature of SRLS is that it always forbids row conflicts. Thus, the number of the cells with each color is exactly n, because each color occurs exactly once in each row, and the focus of the algorithm is on eliminating the existing column conflicts. The use of a limited search space enables the definition of a swap-based neighborhood that is tailored to exclusively address column conflicts. By narrowing the search space, a more effective and targeted solution to this issue can be devised. SRLS first applies two newly proposed reduction rules to simplify the problem instances and randomly generates an initial solution without row conflicts (line 1). Then, it iteratively improves the solution by the local search procedure (lines 3-11). At each iteration, it first evaluates the neighborhood of the current solution and selects the best move based on two scoring functions and a tabu strategy (line 4). Then, it performs the best move for the current solution (line 5). Afterwards, if the current solution C is a legal Latin square, i.e., |CE (C) | = 0, the current solution is returned (lines 6-7). Otherwise, it compares the quality of the current solution C with the best found solution C ∗ (lines 8-11). If C is not worse than C ∗ , i.e., |CE (C) | ≤ |CE (C ∗ ) |, then C ∗ is replaced with C (lines 8-9). Otherwise, the local search is adaptively restarted from the best found solution if necessary (lines 10-11). Finally,

Algorithm 1 The main framework of the SRLS algorithm

Input: A Latin square graph G = (V, E)

Output: A coloring solution C

• 1: A coloring solution C ← Initialize (G) // Algorithm 2 2: The best found solution C ∗ ←C 3: while elapsed time < time limit do 4: Select the best move m(u, v) based on the neighborhood evaluation and tabu strategy 5: C ←C ⊕m(u, v) // swap the colors of u and v 6: if |CE(C)| = 0 then 7: return C 8: else if |CE(C)| ≤ |CE(C ∗ )| then 9: C ∗ ←C // replace the best found solution 10: else 11: C ←AdaptiveRestart (C,C ∗ ) // Algorithm 3 12: return C ∗

Algorithm 2 Initialization

Input: A Latin square graph G = (V, E), vertex set FC for whose colors were fixed

Output: A coloring solution without row conflicts C

• 1: Initialize a color domain D(v) for each cell v ∈ V
• 2: for i = 1 to n do
• 3: RCi ← {1, . . . , n} // initialize row conflict-free color
• 4: RV ′ i ←RVi // copy the row cells
• 5: while ∃v ∈ FC was not propagated do
• 6: Propagate based on FC to update color domains
• 7: for ∀v /∈ FC and |D(v)| = 1 do
• 8: FC ←FC ⋃{v}
• 9: for ∀vij ∈ FC with color domain D(vij) = k do
• 10: RV ′ i ←RV ′ i \{vij} , RCi ← RCi \{k} // update row cells and row conflict-free colors
• 11: for i = 1 to n do
• 12: for all v ∈ RV ′ i do
• 13: Select a random color c from RCi
• 14: C (v) = c // assign a random row conflict-free color to the uncolored cell
• 15: RCi ←RCi \ {c}
• 16: return C

once the elapsed time exceeds the time limit, SRLS terminates and returns the best solution C ∗ (line 12).

3.2 Initialization

We propose two reduction rules to reduce the color domains of some cells. Note that if the color domain of a cell is reduced to a single value, the color of the cell is fixed.

Reduction Rule 1: Let SV be a set of cells in a row (column) and DS = ⋃v∈SV D(v). If |DS| = |SV |, then the colors in DS cannot be used to color other cells in the same row (column), and should be removed from the domains of these cells.

Reduction Rule 2: Let SV be a set of cells in a row (column) and CS be a set of colors. If |CS| = |SV | and the colors in CS can only be used to color the cells in SV and cannot be used to color other cells in the same row (column), then the colors not in CS should be removed from the domain of each cell of SV .

Note that the three reduction rules proposed in MMCOL [2019] and FastLSC [2022] are the special cases of our rules for |SV | = 1.

Rule 1 and Rule 2 can be implemented by calling the constraint programming solver, such as Choco [Prud'homme et al., 2019] with all-different constraints. We construct the model with 2n all-different constraints and repeatedly propagate the constraints until there are no more cells whose colors can be fixed. Experiments showed that our reduction rules can reduce more color domains, and can fix more cells than the previous reduction rules.

Let RCi (i = 1, . . . , n) denote the set of colors, called row conflict-free colors, such that coloring any cell on the ith row with any color in RCi will not lead to a row conflict. The initialization procedure is shown in Algorithm 2. SRLS repeatedly applies the all-different propagator to update the color domains until no cell can be colored with a fixed color (lines 5-8). After that, SRLS updates the row conflict-free colors based on the cells whose colors are fixed (lines 9-10). Then, an initial solution without row conflicts is randomly generated (lines 11-15). Specifically, for each uncolored cell uij, it is colored with a random color c from RCi (line 14), and then RCi is updated (line 15). Finally, an initial solution without row conflicts is returned (line 16).

3.3 Neighborhood Structure and Evaluation

In order to improve the initial solution, we employ a swapbased neighborhood structure. Denoted by m(u, v), a swap move produces a neighboring solution C ⊕ m(u, v), by exchanging the colors of cells u and v on the same row whose colors are not fixed. For a move m(u, v), u and v are called operation cells. Different from the strategies in previous literatures which always satisfy the color domain constraint, i.e., Constraint (2), we relax this constraint when performing a swap move. Specifically, for a move m(u, v), even if C (v) /∈ D(u) (resp. C (u) /∈ D(v)), cell u(resp. v) can still be colored with C (v) (resp. C (u)). Note that the relaxation of the color domain is essential in our algorithm since it allows the search to connect high-quality solutions via the solutions with color domain violations. The problem with color domain relaxation can be formulated as follows:

Note that Constraint (6) stipulates that the row conflict is always forbidden.

The neighborhood evaluation is the most time-consuming part in a trajectory-based metaheuristic algorithm. For a typical local search algorithm which adopts the best improvement policy, it evaluates all feasible moves at each iteration, and performs the best move to optimize the scoring objectives as much as possible. If we evaluate the whole neighborhood, i.e., exchanging the colors of any two cells on the same row, there will be O (n3 ) swap moves, which is huge for large instances. Therefore, in order to reduce the scale of the neighborhood and preserve most high-quality neighboring solutions, we only evaluate the moves where at least one operation cell is conflicting. Note that a legal solution can be obtained by only performing on the conflicting cells, because a legal Latin square is an n-coloring of the associated Latin square graph without conflicting cells. Thus, if the number of conflicting cells whose colors are not fixed in the current solution is p, the size of the neighborhood will be O (pn) which is far smaller than O (n3 ).

Figure 1 presents an example of the relaxation-based swap move including a partial Latin square of order 4 with 4 filled cells. The numbers in cells represent the colors of the cells. The numbers in triangle denote that the colors are fixed, while the numbers in circle denote that the cells are conflicting and the edges connecting them represent the conflicting edges. One can observe that move m (v33, v34) can produce a neighboring solution which reduces one conflicting edge. Note that since the color of cell v14 is fixed, this move leads to a color domain violation, i.e., C (v34) /∈ D (v34).

In the local search procedure, the neighborhood evaluation is an important ingredient. To obtain the best neighboring solution and improve the incumbent solution C, two scoring functions are employed by SRLS. Since the number of conflicting edges is the optimization objective, the primary scoring function is defined as minimizing the number of conflicting edges |CE (C) |. For a move m(u, v) producing a neighboring solution C ′ , it is evaluated as follows:

In order to distinguish multiple swap moves with the same primary scoring function value, SRLS adopts a secondary scoring function which plays an important role in the search. A secondary scoring function can successfully mitigate the gradient vanishing issue and guide the search to a promising direction in many local search algorithms [Chen et al., 2021; Li et al., 2020; Zhang et al., 2022]. For a cell v, if the color domain of cell v is violated, i.e., C (v) ̸∈ D(v), it implies that cell v is conflicting with another cell whose color is fixed, and this will lead to an illegal solution no matter what colors of the remaining cells are. For two solutions having the same number of conflicting edges, the one with fewer color domain violations is usually easier to be repaired to a legal solution. Therefore, the secondary scoring function is defined as minimizing the number of color domain violations |DV (C) |. Specifically, for a move m (u, v) producing a neighboring solution C ′ , it is calculated as follows:

Algorithm 3 Adaptive Restart

Input: Current solution C, the best found solution C ∗ Output: Input solution C for the next round of local search

• 1: Initialize at the first call: accu ← 0, rt ← rt0 // initialize the restart threshold
• 2: if |CE(C)| - |CE(C ∗ )| > rt then
• 3: C ←C ∗ // restart from the best found solution // increase the threshold rt by one for every accuub restarts from C ∗ without exceeding rtub
• 4: if rt < rtub then
• 5: accu ← accu + 1
• 6: if accu = accuub then
• 7: accu ← 0 // reset
• 8: rt ← rt + 1
• 9: return C

The intuitions of ∆f1 and ∆f2 lie in the fact that ∆f1 reflects the immediate impact, while ∆f2 can be considered as the potential impact. In detail, at each iteration, SRLS picks a move with the smallest ∆f1 value, and ties are broken by choosing the one with the smallest ∆f2 value. If ∆f2 values are still the same, ties are broken randomly. For more exploration, if all the neighboring solutions increase the number of conflicting edges, i.e., ∆f1 > 0, SRLS will randomly choose a conflicting cell v and select the best move associated with v based on the scoring functions. By combining these two scoring functions, SRLS can not only easily connect high-quality solutions via the solutions with color domain violations, but also minimize the number of color domain violations as soon as possible as the local search proceeds.

3.4 Tabu Search

We employ a tabu strategy in our local search. Tabu search usually incorporates a recency-based tabu list to avoid reevaluating the just-visited solutions [Glover and Laguna, 1998]. For the tabu list, once a move is performed, the conflicting operation cell is forbidden to be recolored with the original color for the next l iterations. Specifically, for a move m(u, v), if u(v) is a conflicting cell, (u,C (u)) ((v,C (v))) is recorded in the tabu list. Here, the tabu tenure l is determined by l = α ∗ |CE (C) | + r(10), where r (10) takes a random number in {1, . . . , 10} [Galinier and Hao, 1999].

A move m(u, v) is declared to be tabu if coloring one cell with the color of another one is in the tabu list, i.e., (u, C (v)) or (v,C (u)) is in the tabu list. Besides, we adopt a simple aspiration criterion that a move is permitted to be selected in spite of being tabu if it leads to a solution better than the best found solution. Note that we select the best tabu move and the best non-tabu move both based on the two scoring functions mentioned above. At each iteration, the best tabu move is selected as the final move only if it is better than the best non-tabu move and it can lead to a solution whose number of conflicting edges is smaller than that of the best found solution. Otherwise, the best non-tabu move is selected.

3.5 Adaptive Restart Mechanism

Different from the classic graph coloring problem [Garey and Johnson, 1979], the symmetry of the LSC problem solution is weak since the colors of some cells have been fixed. Thus, it is more difficult for the LSC problem to escape from a poor solution trap than the classic graph coloring problem. A restart mechanism can often help the search to break such predicaments [L¨u and Hao, 2012; Wu and Hao, 2013]. Therefore, if the solution quality becomes poor enough, we employ an adaptive restart mechanism to intensify the search by restarting from the best solution found so far.

Algorithm 3 implements such an adaptive restart mechanism using three parameters rt0, rtub and accuub. The key of the mechanism is a restart threshold rt. When the gap of the number of conflicting edges between the current solution C and the best solution found so far C ∗ exceeds rt, SRLS gives up C and restarts the local search from C ∗ (lines 2-3). Meanwhile, the tabu list will be cleared after restarting. For balancing the exploitation and exploration of the search, rt is initialized to a small value rt0, and increased by one for every accuub such restarts without exceeding rtub to make the search restart fromC ∗ less often (lines 4-10).

4 Experiments and Analysis

To assess the performance of the proposed SRLS algorithm, we conduct comprehensive experiments on totally 1819 public benchmark instances. We compare the results of our algorithm with two exact solvers, Gurobi 11.0.0 and CP-SAT solver in OR-tools 9.7.2996, and six state-of-the-art heuristics, including four iterated local search algorithms (i.e., 1ILS*, 2-ILS, 3-ILS and Tr-ILS*) [2016], MMCOL [2019] and FastLSC [2022], which are the best-performing algorithms to the best of our knowledge for the LSC problem.

4.1 Experimental Protocol

Our proposed SRLS algorithm 1 is implemented in C++ and compiled by Visual Studio 2017. The code for the reference algorithms was kindly provided by their respective authors. All experiments are carried out on Intel Xeon E5-2698v3 @ 2.30GHz CPU with 192GB RAM under Windows Server 2012 x64 and only a single thread is used per run.

There are mainly two sets of benchmark instances for the LSC problem. The first set consists of 1800 random LSC benchmark instances 2 which are classified into 18 types, each type containing 100 instances [Haraguchi, 2016]. Each type is named QWH-n-r, where n denotes the order of Latin square and r denotes the ratio of filled cells over the n×n grid of cells. The second set consists of 19 traditional benchmark instances from the COLOR03 competition 3 . For each instance, our algorithm is executed independently for 30 times with random seeds ranging from 1 to 30 under two time limits: 10 and 1000 seconds.

1 The executable code of SRLS algorithm is online available at https://github.com/cardal1/SRLS.

2 https://github.com/YanJINFR/Latin-Square-Completion

The parameters of SRLS are tuned using the automatic configuration tool, irace [L´opez-Ib´a˜nez et al., 2016]. We randomly select 300 instances as the training set which are chosen from all of the 1819 instances. The tuning process is given a budget of 9000 runs, each with a time limit of 1000 seconds. The final parameter values obtained by irace are shown in Table 1. Additionally, experiments were conducted on all possible combinations of the parameter values on the training subset, which revealed that the best parameter settings have an average of 1.02% higher success rate than other combinations of parameters. This underscores the robustness of our SRLS algorithm against parameter variations.

4.2 Computational Results

The comparison results of SRLS and the reference algorithms are presented in Tables 2-6. Note that "tl" represents the time limit. Column "#solv" denotes the total number of solved runs under the time limit. Column "SR(%)" displays the percentage of solved runs under the time limit. Column "t (s)" describes the mean computational time over the runs where a legal solution is obtained by the algorithm. Column "tavg (s)" indicates the average value of t (s), which is calculated over the instances in the same instance type. The numbers in bold stand for the best solution.

Table 2 displays the results obtained with a time limit of 1000 seconds by OR-tools, Gurobi and our SRLS on all instances. One can observe that our SRLS algorithm achieves over 90% success rate across all instance types, while for the state-of-the-art exact solvers, they solved much fewer instances on all the instance types, especially when n is large.

Table 3 presents the results obtained on 1800 random instances with a time limit of 10 seconds. One can observe that our SRLS algorithm achieves the highest success rate across all instance types, especially for the instances which are filled with 70% cells. Furthermore, SRLS demonstrates an average speedup of 8-106 times over the state-of-the-art algorithms. Notably, the performance of SRLS, FastLSC and MMCOL dominates that of the remaining four algorithms (i.e., 1-ILS*, 2-ILS, 3-ILS and Tr-ILS*). This phenomenon also happens under other time limits or on other benchmarks. Therefore, in the following part, we mainly compare SRLS with FastLSC and MMCOL.

3 http://mat.gsia.cmu.edu/COLOR03/

Table 4 shows the comparison results tested under the time limit of 1000 seconds on the random instances. Instances that can be solved by all the algorithms under the 10-second limit are excluded. One can observe that SRLS solves for all runs except for 10 runs on QWH-50-70, which shows its superiority over the state-of-the-art algorithms. Furthermore, the average computational time of SRLS is significantly shorter than that of other reference algorithms.

Table 5 presents the detailed results on 13 challenging instances, out of the 1800 random instances, on which both MMCOL and FastLSC are unable to solve for all runs under the 1000-second time limit. The results indicate that SRLS is able to solve 12 out of the 13 challenging instances for all 30 runs, while for the remaining one instance (i.e., QWH-50-7057), SRLS still outperforms MMCOL and FastLSC, with 20 runs solved compared to 4 and 8 runs, respectively.

Table 6 displays the experimental of MMCOL, FastLSC and SRLS on the 19 traditional instances with the time limits of 10s and 1000s. SRLS outperforms both MMCOL and FastLSC with higher success rates and shorter computational time on almost all these instances. In particular, for the extremely difficult instance (i.e., qwhdec.order50.holes750 [Kautz et al., 2001]) where both MMCOL and FastLSC failed to solve within 1000s, SRLS achieves a success rate of 7/30, demonstrating its effectiveness and efficiency.

4.3 Analysis and Discussion

In order to evaluate the merits of the reduction rules, the color domain relaxation technique, the secondary scoring function and the adaptive restart mechanism employed in the SRLS algorithm, we conducted experiments on three difficult and representative instances (i.e., QWH-50-70-100, QWH-50-70-26 and QWH-60-70-50) by comparing SRLS against its alternative variants with specific components disabled.

These variants include SRLS RD (use previous reduction rules proposed in FastLSC [2022] to reduce color domains instead of those proposed in this paper and used in SRLS), SRLS RL (disable the color domain relaxation technique), SRLS f2 (deactivate the secondary scoring function), SRLS RS1 (disable the adaptive restart mechanism) and SRLS RS2 (restart the local search every 105 iterations).

Figure 2 depicts the evolution of the solved runs of instances as the search proceeds by SRLS, SRLS RD, SRLS RL, SRLS f2, SRLS RS1 and SRLS RS2. Each point (x, y) on the curves represents that the instance is solved for y runs within x seconds. One can observe that all these three strategies play important roles in the overall performance of SRLS. In particular, the simplified version without the color domain relaxation technique (i.e., SRLS RL) performs the worst. The reason for this phenomenon might be that the connectivity of the solution space in SRLS RL is poor, while the relaxation of the color domain significantly improves the connectivity of the search space. Moreover, although the simplified versions of SRLS are outperformed by SRLS, some of them are still highly competitive compared with the state-ofthe-art algorithms listed in Table 5.

5 Conclusion

This paper presented a swap relaxation-based local search algorithm to solve the LSC problem. By forbidding row conflicts, we define a novel search space and an associated swapbased neighborhood. In addition, we relax the color domain to expand the search space, which enables the search to easily connect high-quality solutions. Finally, we solve the LSC problem by combining two effective scoring functions and a novel adaptive restart mechanism. Tested on 1819 public benchmark instances, SRLS outperforms the state-of-the-art algorithms in terms of both success rate and computational efficiency. Since the LSC is essentially a classical multiple permutation problem of which the structure is common in CSP [Walsh, 2001; Hnich et al., 2004], we plan to adapt the techniques proposed in this paper (such as the relaxation-based neighborhood, the secondary scoring function and the adaptive restart mechanism) to solve other challenging combinatorial optimization problems in the future.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 72101094 and 62202192, and the Special Project for Knowledge Innovation of Hubei Province under Grant 2022013301015175.