Variable-Oriented Adaptive Singleton Consistency

1 Introduction

Constraint propagation is the cornerstone of solving constraint satisfaction problems. It enforces local consistencies to prune the search space of backtracking search. Generalized arc consistency (GAC) [Bessi`ere and R´egin, 1997] has been the most popular level of local consistency in constraint solvers. In the past decades, a number of consistencies that are stronger than GAC have been developed [Debruyne and Bessi`ere, 1997; Bennaceur and Affane, 2001; Bessi`ere et al., 2008; Lecoutre et al., 2013; Karakashian et al., 2010]. However, these stronger consistencies are generally too expensive to be used during the whole search. Thus, some efforts have been made on adaptive consistency [Stergiou, 2008; Paparrizou and Stergiou, 2012; Balafrej et al., 2013; Balafrej et al., 2014; Woodward et al., 2014; Balafrej et al., 2015; Woodward et al., 2018]. These studies demonstrate the potential of adaptive consistencies for enhancing the performance of backtracking search. However, most of them focus on particular kinds of problems defined with specific constraints, such as binary constraints [Stergiou, 2008;

∗ corresponding author

Balafrej et al., 2013; Balafrej et al., 2015], and table constraints [Paparrizou and Stergiou, 2012; Woodward et al., 2014]. To the best of our knowledge, none of them has been applied in general-purpose constraint solvers.

In constraint solvers, the default propagation engines usually employ GAC and bound consistency (BC) [Collavizza et al., 1998] for most of the constraints. It is non-trivial to implement the stronger consistencies concerning multiple constraints, such as maxRPC [Debruyne and Bessi`ere, 1997] and maxRPWC [Bessi`ere et al., 2008]. On the contrary, singleton consistency is relatively easier to implement in generalpurpose solvers.

In this paper, we investigate how to improve the performance of a general-purpose constraint solver by utilizing the stronger filtering ability of singleton consistency. We propose a variable-oriented adaptive singleton consistency (namely VOASC) that can be applied in general-purpose constraint solvers. It considers switching between the local consistency enforced by the default propagation engine, denoted by default local consistency (DLC), and the singleton consistency (SC) [Debruyne and Bessi`ere, 1997] built on DLC. We evaluate the filtering efficiency of a candidate consistency by the number of values filtered by it per unit time. At each subsequent search tree node, we select an unassigned variable and then determine whether the DLC or the SC should be used to propagate the assignment of the variable according to their filtering efficiencies. Furthermore, we adapt the method to apply it in solving constraint optimization problems (COP). We performed extensive experimentation with the MiniZinc benchmark suite. The experiments were conducted in Choco solver under three efficient variable ordering heuristics, dom/wdegca.cd [Wattez et al., 2019], FRBA [Li et al., 2021] and pick/dom [Audemard et al., 2023]. VOASC is compared with the DLC, the SC, and some adaptive propagation methods, including an existing adaptive singleton-based consistency [Balafrej et al., 2014], a reinforcement-learningbased adaptive propagation method [Woodward et al., 2014], and a reactive propagation strategy PrePeak+ [Woodward et al., 2018]. The results demonstrate the superior solving performance of VOASC on both CSP and COP.

2 Background

A constraint satisfaction problem (CSP) P is a triple P = ⟨X , D, C⟩, where X is a set of n variables X ={x1, x2, ..., xn}, D is a set of domains D ={dom(x1), dom(x2), ..., dom(xn)}, where dom(xi) is a finite set of possible values for variable xi, and C is a set of e constraints C={c1, c2, ..., ce}. Each constraint c consists of two parts, an ordered set of variables scp(c) = {xi1, xi2, ..., xir} and a subset of the Cartesian product dom(xi1) × dom(xi2) × ... × dom(xir) that specifies the allowed combinations of values for the variables {xi1, xi2, ..., xir}. An element of dom(xi1) × dom(xi2) × ... × dom(xir) is called a tuple on scp(c), denoted by τ. τ[xi] is the value of xi in τ. A tuple τ is valid iff for each xi ∈ scp(c), τ[xi] is in dom(xi). We use P(xi = v) to denote the CSP obtained by restricting dom(xi) to {v} in P. An assignment A to variables X ⊆ X is a set of instantiations of the form (xi = v), one for each xi ∈ X to assign v to xi where v ∈ dom(xi). An assignment to X satisfying all constraints is a solution to P.

A CSP is satisfiable if it has at least one solution; otherwise unsatisfiable. Solving a CSP involves either finding a solution or determining that no solution exists. Backtracking search is widely used in solving CSPs. It performs a depthfirst traversal of a search tree. At each search tree node, an unassigned variable is selected, typically using a variable ordering heuristic (VOH), and a new node is generated after the instantiation of this variable; then a propagation algorithm is applied to filter those inconsistent values [Bessi`ere, 2006]. If the propagation of the current decision leads to failure, e.g., a domain wipeout, then one or more decisions must be canceled, and backtracking occurs.

When an objective function F is added to a CSP, we obtain a constraint optimization problem (COP). The objective function F maps every feasible solution to a real number, called the objective. Solving a COP P involves finding an optimal solution, which is the feasible solution of P with the best objective. However, for many real-world COP scenarios, finding a high-quality solution quickly is often the primary requirement. When solving a COP, backtracking search is adapted into branch-and-bound search (B&B). The decision process and propagation process in solving CSPs and COPs are similar, the difference is that whenever a new feasible solution S is found by B&B, F(S) is used to bound subsequent search to ensure the next feasible solution found must be better than S. Search continues until no more feasible solutions are found after exhausting the search space. The last solution found is an optimal solution of P.

Definition 1 (Generalized Arc Consistency). Given a CSP P = ⟨X,D, C⟩, a constraint c ∈ C, and a variable xi ∈ scp(c),

• A value (xi = v) is consistent with c iff there exists a valid tuple τ allowed by c and τ [xi] = v.
• A constraint c is generalized arc consistent iff ∀xi ∈ scp(c), dom(xi) ̸= ∅ and ∀v ∈ dom(xi), (xi = v) is consistent with c.
• P is generalized arc consistent iff all the constraints of C are generalized arc consistent.

While GAC checks the consistency of all the values in the domain of each variable, bound consistency checks only the lower bound and upper bound of the domain of each variable. The DLC of a CSP solver usually contains different consistency levels. For example, it may enforce BC for linear constraints, and GAC for table constraints [Lecoutre, 2011] and some global constraints [R´egin, 1994].

Singleton consistency was first proposed as singleton arc consistency (SAC) 1 [Debruyne and Bessi`ere, 1997]. SAC can be extended to a more general singleton consistency that replaces the underlying consistency, AC, with other local consistencies, such as GAC or even the DLC of a constraint solver. In this work, we use DLC as the underlying consistency. In the following, singleton consistency (SC) denotes the singleton consistency built on the DLC of a constraint solver. DLC(P(xi = v)) is the CSP after assigning v to xi and running the DLC. Given a CSP P, for each variable-value pair (xi, v), the SC checks and removes the v from dom(xi) if DLC(P(xi = v)) leads to a failure.

Besides constraint propagation, the restart technique [Gomes et al., 1998] makes constraint solvers more robust in solving various types of problems. It terminates the run of the current search and restarts a new search from the root node when a predefined restart condition is reached. The aim is to switch search entrances to prevent the search from being trapped in exploring a part of the search space far from a solution. It has been shown that a sequence of short runs instead of a single long run may be a more effective use of computational resources [Gomes et al., 2000].

3 Variable-Oriented Adaptive Singleton Consistency

In constraint solvers, singleton consistency (SC) is more powerful in filtering inconsistent values than the default local consistency (DLC). However, in some cases, SC costs much more computational resources than DLC, yet achieves only marginally better filtering performance. Thus, the key issue is to determine when singleton consistency should be applied, ensuring computational resources are allocated exclusively to effective domain filtering. To address the issue, we develop a variable-oriented adaptive singleton consistency. The method dynamically evaluates the performance of different consistencies propagating the decisions of each variable, and determines the most effective consistency for the variable, which could yield better filtering performance. In the following, we first introduce the evaluation of the filtering performance of different consistencies, and then propose the adaptive singleton consistency based on the evaluation.

3.1 Evaluation of Filtering Performance

To evaluate the filtering performance of a local consistency LC, we consider the number of values filtered by LC per unit time, called filtering efficiency (FE). When a local consistency LC is applied to propagate the decision of a variable xi, we count the total number of values filtered by the propagation (marked by filterNum) and record the time cost (marked by duration) of the propagation, then we can calculate the FE of the propagation by filterNum duration . For each variable xi, we use a counter proNumLC[i] for the number of propagations on xi with LC, and an accumulator accFELC[i] to aggregate the FEs generated during these propagations. Then

1 Arc consistency (AC) is the GAC in binary CSPs.

Algorithm 1: ADAPTIVE PROPAGATION

Input: xi: a variable; v: a value in dom(xi) Output: isConsistent: boolean 1 before ← sum of the domain size of all variables; 2 scTriggered ← ISSINGLETONCONSISTENCY(xi); 3 startTime←current timestamp; 4 if scTriggered then 5 isConsistent ← SCPROPAGATE(xi, v); 6 else 7 isConsistent ← DLCPROPAGATE(xi, v); 8 duration←current timestamp - startTime; 9 after ← sum of the domain size of all variables; 10 filterNum←before - after; 11 FE← filterNum duration ; 12 if scTriggered then 13 proNumSC[i] ←proNumSC[i] +1; 14 accFESC[i] ←accFESC[i]+ FE; 15 else 16 proNumDLC[i] ←proNumDLC[i] +1; 17 accFEDLC[i] ←accFEDLC[i]+ FE; 18 return isConsistent;

we can calculate the average FE of propagating xi with LC by accFELC[i] proNumLC[i] , marked by aveFELC[i].

Given two local consistencies of a constraint solver, DLC and SC. We can calculate the scores for them on each variable xi, e.g., aveFEDLC[i] and aveFESC[i], and the one with the larger score is preferred to propagate the decisions of xi.

3.2 The Adaptive Propagation Algorithm

The adaptive propagation algorithm is presented in Algorithm 1 and Algorithm 2. The Algorithm 1 is called at each search tree node to adaptively select a local consistency to propagate the decision of xi.

Algorithm 1 selects a candidate consistency at line 2 by the function ISSINGLETONCONSISTENCY presented in Algorithm 2, and then the selected consistency is employed to propagate the decision of xi at line 5 (by SC) or line 7 (by DLC). The propagation result, e.g., a failure is detected or not, is also recorded here. The duration of the propagation is obtained at line 8, the number of filtered values is calculated at line 10, and the FE of the propagation is calculated at line 11. The counter proNumSC[i] is updated at line 13, and the accumulator accFESC[i] is aggregated at line 14. The corresponding data of DLC are updated at lines 16-17. Finally, the propagation result is returned at line 18.

Algorithm 2 determines whether SC should be applied to propagate the decision of xi. Our study originates from tackling the problem instances that are hard for DLC to solve, so we employ a preprocessing phase at the beginning of the resolution to eliminate the easy instances, so that only the hard instances proceed to the next phase that activates the adaptive singleton consistency.

In the preprocessing phase, the search always selects DLC to propagate the decisions of all variables. The preprocess-

Algorithm 2: ISSINGLETONCONSISTENCY

Input: xi: a variable Output: true for SC; false for DLC; 1 if preProcessing then 2 if restartNum< preLimit then 3 for j = last to |X | - 1 do 4 if proNumDLC[j] = 0 then 5 last ← j; 6 return false; 7 preProcessing← false; 8 if proNumDLC[i] > 0 and proNumSC[i] > 0 then 9 aveFEDLC[i] ← accFEDLC[i] proNumDLC[i] ; 10 aveFESC[i] ← accFESC[i] proNumSC[i] ; 11 return aveFEDLC[i] < aveFESC[i]; 12 else if proNumDLC[i] > 0 and proNumSC[i] = 0 then 13 return true; 14 else if proNumDLC[i] = 0 and proNumSC[i] > 0 then 15 return false; 16 else 17 dlcBetter ← 0; 18 scBetter ← 0; 19 for k = 0 to |X | - 1 do 20 if proNumDLC[k] > 0 and proNumSC[k] > 0 then 21 aveFEDLC[k] ← accFEDLC[k] proNumDLC[k] ; 22 aveFESC[k] ← accFESC[k] proNumSC[k] ; 23 if aveFEDLC[k] ≥ aveFESC[k] then 24 dlcBetter ← dlcBetter + 1; 25 else 26 scBetter ← scBetter + 1; 27 return dlcBetter < scBetter;

ing phase terminates when either a limited restart number preLimit (a parameter) is reached or all variables have the FE information of DLC. In Algorithm 2, the preprocessing (initialized to true) and last (initialized to 0) are global variables. The restartNum is also a global variable that records the restart number. If restartNum is larger than preLimit, the preprocessing label is set to false at line 7; otherwise, it checks whether there are variables lacking FE information at lines 3-6. If proNumDLC[j] is 0, it indicates that the variable xj has never been propagated by DLC and has no FE information, so the resolution is still in the preprocessing phase and xi should be propagated by DLC (false is returned at line 6). Note that the last records the last variable identified as lacking FE information and it is used globally. When checking whether there are variables lacking FE information, we start from the last identified one. If all variables already have FE information, the preprocessing label will be set to false at line 7. After the preprocessing phase is terminated, given a variable xi, the adaptive selection is divided into four cases:

(1) both SC and DLC have FE information; (2) DLC has FE information and SC does not; (3) SC has FE information and DLC does not; (4) neither of them has the information.

Whether a candidate has FE information on a variable xi can be reflected by the proNumLC[i], i.e., proNumLC[i] > 0 indicates that the candidate LC has FE information. The first case is confirmed at line 8, and then we calculate the aveFEDLC[i] and aveFESC[i] at line 9 and line 10, respectively. The selection will be made at line 11.

In cases (2) and (3), we prefer to select the one lacking FE information. Thus, in the second (or third) case confirmed at line 12 (or line 14), our strategy is to directly select SC (or DLC) at line 13 (or line 15).

In the last case, none of the candidates has FE information on xi. This happens only when the preprocessing phase is terminated by the restart limit (the condition at line 2) and xi has never been assigned during the preprocessing phase. We use the FE information of other variables to determine which candidate should be tried first on xi. Specifically, we choose the variables that have learned FE information for both SC and DLC (the variables identified at line 20) to vote for the decision. We use two counters dlcBetter and scBetter to record the number of variables voting for the candidates, respectively. For each voter variable xk, the aveFEDLC[k] and aveFESC[k] are calculated at line 21 and line 22, respectively. The voting choice is made at lines 23 to 26, and the final decision is made at line 27.

In binary branching [Hwang and Mitchell, 2005], Algorithm 1 is used to propagate only positive decisions, and the candidate consistency used to propagate each positive decision is recorded. If the search backtracks and the corresponding negative decision is generated, then the recorded consistency will be used to do the propagation directly.

3.3 Adaptation for COP

The method introduced before is designed for solving CSPs. It can be directly applied in solving COPs. However, solving a COP involves solving a series of CSPs. With the bounds of the objective being tightened, the newly generated CSPs become increasingly difficult to solve. Consequently, the FE information gathered through the initial preprocessing procedure may lose its effectiveness. To address the issue, we rerun the preprocessing procedure when we find it difficult to find a new solution. There are various criteria for determining when a problem enters a hard-to-solve phase. We employ a simple strategy here, which triggers the preprocessing procedure when no new feasible solution is found after q restarts, where q is a parameter.

4 RelatedWork

The following approaches can be considered as constraintoriented adaptive constraint propagation, since they associate each constraint with a local consistency. (1) Stergiou proposed adaptive propagation approaches [Stergiou, 2008] that use some heuristics to dynamically switch between enforcing a weak local consistency (AC) and a strong local consistency (maxRPC). The heuristics monitor the DWO (domain wipe out) and the value deletions led by each constraint. If a constraint leads to a DWO in current propagation or it deletes at least a value, it will be propagated by the strong local consistency at the next time. Later, Paparrizou and Stergiou extended the approach to non-binary CSPs [Paparrizou and Stergiou, 2012], e.g., the weak local consistency is GAC, and the strong local consistency is maxRPWC. (2) Stamatatos and Stergiou proposed to run a random probing preprocess [Stamatatos and Stergiou, 2009] to learn which local consistency should be used on each constraint. It gathers information regarding the percentage of fruitful revisions for each constraint and the values filtered by different propagation methods, e.g., BC, AC and maxRPC. Consequently, the constraints can be clustered and the solver could automatically choose the local consistency for each constraint.

The following approaches can be considered as nodeoriented adaptive constraint propagations, since they choose to enforce a specific local consistency at certain search tree nodes according to some heuristic. (1) The adaptive partitionone-AC (APOAC) [Balafrej et al., 2014] is an adaptive singleton consistency which is closely related to our method. It interrupts the propagation process (in particular, the singleton tests) when the pruning effect of the singleton tests has faded. Specifically, APOAC alternates between a learning phase and an exploitation phase during search. In the learning phase, it tries to learn a value k for the maximum times that a series of singleton tests on all values of a variable should be performed in the exploitation phase. The main idea of APOAC can be applied to other singleton consistencies, and we will compare its adaptation of SC with our method in the experiments. (2) The adaptive propagation method [Balafrej et al., 2015] based on reinforcement learning switches among AC, maxRPC and POAC at each depth of the search tree. It associates each depth with a multi-armed bandit (MAB) selector that prefers the local consistency i that maximizes:

where Ri is the mean of the past rewards of local consistency i at the current depth, mi is the number of times local consistency i was selected and m is the current number of all trials. The reward is the CPU time needed to enforce local consistency i at the m-th visit of a node at the given depth plus the time to explore the subtree rooted there. (3) The last one we should mention is a reactive strategy that triggers strong local consistency when the search starts thrashing, namely PrePeak [Woodward et al., 2018]. Specifically, it records the backtrack times of each search tree level and uses a threshold θ to determine whether the strong local consistency should be triggered at the current level. The θ is initialized to the maximum value of the recorded backtrack times in the first n2 backtracks, and it is increased (or decreased) if applying the strong local consistency leads to a failure (or not). A variant of PrePeak, namely PrePeak+ employs a strategy to terminate the propagation of the strong local consistency either by the size of the propagation queue or by the run time.

5 Experiments

To examine how the variable-oriented adaptive singleton consistency performs in general-purpose constraint solvers, we perform extensive experimentation with the MiniZinc benchmark suite [Stuckey et al., 2014]. The following are some detailed settings of the experiments:

• Environment. The environment is JDK21 under Ubuntu 24.04 with four Intel(R) Xeon(R) CPU E7-8890v4 @2.20GHz and 512GB RAM. We have 96 cores in total, so 96 test runs are running simultaneously. Each run is allocated with 1 core and 8GB RAM.
• Solver. The experiments were conducted in an efficient and well-architected CP solver, Choco [Prud'homme et al., 2017]. The source code of our algorithm is available at https://github.com/tiger510520/VOASC
• Baselines. We compare VOASC against the two candidate consistencies: the DLC of Choco and the SC built on the DLC. Some adaptive propagation methods including the MAB-based adaptive propagation (denoted by MABAP) [Balafrej et al., 2015], the existing adaptive singleton-based consistency (denoted by ASC) [Balafrej et al., 2014] and PrePeak+ [Woodward et al., 2018], are also involved. These adaptive propagation methods are adopted to make a selection between DLC and the SC.
• Instances. We have considered two CSP instance sets from the MiniZinc benchmark suite. The first set contains 103 instances 2 used in recent MiniZinc challenges (from 14 problems). The second set contains 362 instances (from 46 problems) selected from the MiniZinc instance set 3 available at https://github.com/MiniZinc/ MiniZinc-benchmarks, which will be used in Tables 5 to 6. For the COP experiments, we considered the instances used in the 2024 and 2025 MiniZinc Challenges.
• Search Strategies. We have used three variable ordering heuristics, dom/wdegca.cd [Wattez et al., 2019], FRBA [Li et al., 2021] and pick/dom [Audemard et al., 2023]. The value selector for CSP always selects the minimum value. For COP, the value selector is solutionbased phase saving [Demirovic et al., 2018] with the underlying value selector that selects the minimum value 4 . All the search strategies are equipped with the Luby [Luby et al., 1993] restart with an initial cutoff of 100 and the restart condition is the number of failures.
• Nogood-Recording. All the compared search strategies are equipped with the Reduced nld-Nogoods [Lecoutre et al., 2007].
• Random seed. The random seed 0 is used throughout the experiments, mainly used by variable ordering heuristics to break ties.

2 There are 105 CSP instances used in 2014-2023 years, but two of them are duplicate ones used in two years.

3 After eliminating some large instances which cannot be flattened in 1 hour, there are 46 problems with 1876 instances. For each problem, if there are more than 10 instances, 10 instances are randomly selected; otherwise, all the instances are selected.

4 We also tested the RLARF [Delecluse and Schaus, 2024] heuristic as the underlying value selector, and the value selectors without solution-based phase saving. The presented combination gets the best performance.

• Metrics. For CSP, the performance of searching for the first solution or proving unsatisfiable are measured by the number of instances solved (#Sol in the tables) in a timeout limit of 3600 seconds and the PAR2 score 5 of runtime. For COP, we have used the primal gap [Berthold, 2013] to evaluate the performance of finding feasible solutions and finding solutions with better objectives. For each tested instance, it gives a score between 0 and 1 to each candidate method defined as follows: if the candidate did not find a feasible solution or obj is opposite in sign to the objbest, where objbest is the objective of the best solution found by all candidates and obj is the objective of the solution found by current candidate, it gets 1 score; otherwise, it gets a score |objbest-obj| max{|objbest|,|obj|} . The smaller score indicates a better performance. We also considered the number of instances where optimality is proved.
• In the following tables, the best one in each comparison is highlighted in bold.

5 The PAR2 score of a solver is defined as the sum of all runtimes for solved instances + 2×timeout for unsolved instances, which is used in SAT competition.

Table 1 presents the results of whether restart and lightweight SC perform better. We can see that both the lightweight version of SC and the restart strategy improve the performance of the naive version of the baselines. Thus, in the following experiments, we use the lightweight version of SC for singleton consistency.

Secondly, we examine whether the filtering efficiency is effective in making the selection, e.g., if the FE information is pre-computed offline, how does VOASC perform? The results are presented in Table 2. We can see that although VOASC is outperformed by the virtual strategy, it performs much better than the two candidates. The results show that the FE is effective in making the selection.

Thirdly, we investigate the impact of the parameter preLimit on the performance of VOASC. While a total of 11 values were tested under the dom/wdegca.cd , for the sake of brevity and to highlight the key performance trends, Table 3 presents the results for 6 representative values. We can observe that the optimal performance is achieved at 100. Thus, we set preLimit to 100 for all subsequent experiments.

Next, we evaluate the performance of VOASC against the baseline methods under two distinct variable ordering heuristics: FRBA and pick/dom, providing a more rigorous test of the algorithms' generalizability. The results are presented in Table 4. In the FRBA columns, we can see that both MABAP and PrePeak+ perform better than DLC and SC in both the number of solved instances and PAR2 score. VOASC brings significant improvement over the existing approaches. It solves 11 more instances than the best baseline, PrePeak+. A similar phenomenon can be observed in the pick/dom columns. Although PrePeak+ works well when combined with pick/dom heuristic, it is still outperformed by VOASC. With both of the variable ordering heuristics, PrePeak+ constructs identical search trees to DLC in much more instances than VOASC, indicating that PrePeak+ prefers to leverage the solving power of DLC. There are only 5 unsatisfiable instances, which may be insufficient to capture the performance characteristics. In addition, since the parameter setting preLimit = 100 was derived from the 103 instance set, we further evaluate the performance of VOASC on the second instance set to verify its generalization capability in Table 5.

The second instance set contains more than 30 unsatisfiable instances. We can see that SC, MABAP and ASC perform much better than the other two baselines in solving unsatisfiable instances under all the three variable ordering heuristics. While PrePeak+ outperforms the other baselines on satisfiable instances, it is only marginally better than DLC on unsatisfiable ones. This observation is consistent with PrePeak+'s tendency to leverage DLC's solving power. When using dom/wdegca.cd , VOASC loses a little in solving unsatisfiable instances in terms of PAR2 score. However, it gets the best performance in all the other comparisons. Its overall performance remains better than that of all the baselines.

Furthermore, we divided the second instance set into four categories and examined how these propagation algorithms perform. The results are presented in Table 6. From the pick/dom columns, we can see that ASC works well in solving the OSC instances, but it cannot solve any ODLC instance, indicating that ASC tends to utilize SC's solving ability. PrePeak+ works well in solving the ODLC instances, but it solves only 1 OSC instance, further confirming that PrePeak+ tends to leverage DLC's solving ability. MABAP and VOASC make a good balance between the utilization of DLC and SC. Both of them successfully solved subsets of instances within ODLC and OSC sets. When comparing VOASC with MABAP, we observe mixed results under the three variable ordering heuristics. However, a notable observation is that VOASC leverages DLC's solving power much more effectively than MABAP, and it solves much more ODLC instances than MABAP. Considering the instances solved by none of DLC and SC, VOASC gets the best performance when using dom/wdegca.cd and pick/dom heuristics, and it is the second best one when using FRBA. Thus, VOASC strikes a superior balance between leveraging the solving power of DLC and SC compared to the existing adaptive approaches.

Finally, we examine how the adaptation of VOASC performs in solving COPs. The results are presented in Table 7. The table presents the results of VOASC adaptation with q = 1000, which is the best parameter (among {100, 200, 500, 1000}) for the adaptation. We can see that SC, ASC and MABAP perform poorly in solving the COP instances. They are significantly outperformed by the other three methods. PrePeak+ is the best one among the baselines, which is reasonable because it tends to leverage DLC's solving ability and the θ is dynamically updated when the newly generated CSP becomes more difficult to solve. However, VOASC still gets a better primal gap than PrePeak+ and proves optimality for more instances than PrePeak+. Note that the direct application of the VOASC algorithm to COPs performs worse than In summary, the filtering efficiency is effective in selecting an appropriate one between DLC and SC to propagate the decision of a variable. VOASC with the parameter tuned on the dom/wdegca.cd heuristic also works well when the heuristics switch to FRBA and pick/dom, which demonstrates the strong generalization capability of our method. VOASC makes better choices about which propagation algorithm to invoke, and it is more robust than the existing approaches in solving both CSPs and COPs.

Table 7: Comparing VOASC against the baselines on the COP instance set. The gap denotes the primal gap, and opt is the number of instances where the optimality is proved.

6 Conclusion

In this paper, we propose a variable-oriented adaptive singleton consistency for solving constraint satisfaction problems. The filtering efficiency of a local consistency is evaluated by the number of total values filtered per unit time. The approach learns the filtering efficiency of singleton consistency and the default local consistency in propagating the decisions of each variable. In the subsequent search, it determines which local consistency should be used to propagate the variable according to the filtering efficiencies. The experimental results show that the filtering efficiency is effective in selecting an appropriate consistency to propagate the decision of a variable. VOASC exploits the potential filtering ability of singleton consistency more effectively than MABAP and PrePeak+. It is also effective to utilize the solving ability of the default propagation engine. Additionally, the adaptation of VOASC also demonstrates superior performance in solving COP compared to existing approaches. In general, VOASC is more efficient and more robust than the existing propagation strategies and it could be an efficient and effective adaptive propagation scheme for general-purpose constraint solvers.

Acknowledgments

We thank the anonymous referees for their constructive comments. This work is supported by the National Natural Science Foundation of China under Grant 62276060, 62532014 and CCF-Huawei Populus Grove Fund.