The Regularization of Small Sub-Constraint Satisfaction Problems

Abstract

This paper describes a new approach on optimization of constraint satisfaction problems (CSPs) by means of substituting sub-CSPs with locally consistent regular membership constraints. The purpose of this approach is to reduce the number of fails in the resolution process, to improve the inferences made during search by the constraint solver by strengthening constraint propagation, and to maintain the level of propagation while reducing the cost of propagating the constraints. Our experimental results show improvements in terms of the resolution speed compared to the original CSPs and a competitiveness to the recent tabulation approach [1, 15]. Besides, our approach can be realized in a preprocessing step, and therefore wouldn’t collide with redundancy constraints or parallel computing if implemented.

1 Introduction

A CSP can be often described in several ways, each of which might consist of different types and combinations of constraints, which leads to various statistical results of the resolution, including the execution time, the number of fails, the number of backtracks, the number of nodes etc. The reason for this is, that the combination of constraints and their propagators have a significant impact on the shape and the size of the search tree. Therefore, the diversity of models and constraints for a given CSP offers us an opportunity to improve the resolution process by using another model in which fewer fails occur during the resolution process. Based on this idea, previous works show that the performance of a constraint problem often can be improved by converting a sub-problem into a single constraint [1,2,3,4, 15].

In this paper, we propose an algorithm which substitutes parts of CSPs by singleton, locally consistent constraints. In contrast to [15], the replacement is based on the regular membership constraint instead of the table constraint. Since our algorithm can be applied at the pre-processing stage, other approaches which accelerate the resolution process such as redundant modeling [6], parallel search [21], or parallel consistency [12] can be used in combination with ours.

The rest of this paper is organized as follows. In Sect. 2, we introduce the necessary notions for the approach. In Sect. 3, the substitution of small sub-CSPs with the regular membership constraint is explained. In Sect. 4, the benefit of our regularization approach is shown in two case studies based on the Solitaire Battleships Problem [9] and the Black Hole Problem [17]. Furthermore, we compare our results with the tabulation approach presented in [15]. Finally, Sect. 5 concludes and proposes research directions for the future.

Remark 1

In this paper we will use the notion of a “regular constraint” synonym for “regular membership constraint”.

2 Preliminaries

In this section, we introduce necessary definitions and methods for our regularization approach. We consider CSPs which are defined in the following way:

CSP [7]. A constraint satisfaction problem (CSP) is defined as a 3-tuple $P = (X,D,C)$ with $X = \{x_1, x_2, \ldots , x_n \}$ is a set of variables, $D = \{D_1,D_2,\ldots$, $D_n\}$ is a set of finite domains where $D_i$ is the domain of $x_i$ and $C = \{c_1, c_2, \ldots , c_m \}$ is a set of primitive or global constraints covering between one and all variables in X.

Additionally, we define a sub-CSP $P_{sub}$ as a part of a CSP $P = (X, D, C)$ which covers only a part of the constraints and their variables.

Sub-CSP. Let $P = (X, D, C)$ be a CSP. For $C' \subseteq C$ we define $P_{sub} = (X',D',C')$ such that $X' = \bigcup _{c \in C'} scope(c)$ with corresponding domains $D' = \{D_i \mid x_i \in X'\} \subseteq D$, where the scope of a constraint c is defined as the set of variables which are part of the constraint c [7].

After we defined CSPs and sub-CSPs, we need a measure for the size of such a CSP or sub-CSP.

size(P). We define the maximal size size(P) of a CSP $P = (X, D, C)$ as the product of the cardinalities of the domains of the CSP P, see Eq. 1.

$$\begin{aligned} size(P) = \prod _{i = 1}^{|X|} |D_i| \end{aligned}$$

(1)

The regular constraint, its propagation [13, 18, 19] and deterministic finite automatons (DFAs) [14] provide the basis of our approach. We briefly review the notion of a deterministic finite automaton (DFA) and of the regular constraint.

DFA [14]. A deterministic finite automaton (DFA) is a quintuple $M = (Q$, $\varSigma$, $\delta$, $q_0$, F), where Q is a finite set of states, $\varSigma$ is the finite input alphabet, $\delta$ is a transformation function $Q \times \varSigma \rightarrow Q$, $q_0 \in Q$ is the initial state, and $F \subseteq Q$ is the set of final or accepting states. A word $w \in \varSigma ^*\;$ is accepted by M, i.e. $w\in L(M)$, if the corresponding DFA M with the input w stops in a final state $f \in F$.

Regular Constraint [19]. Let $M = (Q$, $\varSigma$, $\delta$, $q_0$, F) be a DFA and let $X = \{x_1, x_2, ..., x_n\}$ be a set of variables with $D(x_i) \subseteq \varSigma$ for $1 \le i \le n$. Then

$$\begin{aligned} regular(X,M) = \{(d_1, ..., d_n) | \forall i \; d_i \in D_i, d_1\circ d_2 \circ ...\circ d_n \in L(M)\}, \end{aligned}$$

(2)

i.e. every sequence $d_1...d_n$ of values for $x_1, ..., x_n$ must be a word of the regular language recognized by the DFA M, where $\circ$ is the concatenation of two words.

3 Substitution of Constraints by Regular Constraints

Previous work [4] has shown that each CSP can be transformed into an equivalent one with only one regular constraint (rCSP), theoretically. In this section, we present a practical algorithm to transform the constraints of a sub-CSP $P_{sub}$ of a given CSP P into a regular constraint. For the reason of effectiveness the sub-CSP $P_{sub}$ should be much smaller than the original CSP P (size($P_{sub}) \ll size(P)$).

It is the aim to detect and substitute such sub-CSPs, which are preferably as big as possible but can be represented by a DFA which is as small as possible at the same time. An algorithm to detect such sub-CSPs must be developed in the future. Currently, we use the heuristics to find sub-CSPs given in [1]. Alternatively, an algorithm like Gottlobs hypertree decomposition [11] or Ke Lius det-k-CP [16] can be used.

Our transformation algorithm obtains a sub-CSP $P_{sub} = (X', D', C')$ from CSP $P = (X$, D, C) as input, where $C' \subset C$, $X' = \{x_1,\ldots ,x_n\} = \bigcup _{c \in C'}$ scope(c) $\subset X$, $|X'| \ll |X|$ and $D' = \{D_1,\ldots ,D_n\} \subset D$, where $D_i$ is the domain of variable $x_i, \forall i \in \{1,2,\ldots ,n\}$, and returns a regular constraint which is equivalent to the constraints in $C'$. Our regularization algorithm has two phases:

• 1. Solve the detected/given sub CSP $P_{sub}$.

• 2. Transform all solutions $S = \{s_1,s_2,\ldots ,s_k\}$ of the sub-CSP $P_{sub}$ into a regular constraint.

The first phase is obvious. Notice that the sub-CSP $P_{sub}$ should be much smaller than the original CSP P, otherwise the solving step would be too time consuming.

We continue with a description of the second phase. Let $S = \{s_1,s_2,\ldots ,s_k\}$ be the set of all solutions of $P_{sub}$ calculated in step one. Every solution $s_j$, $j \in \{1,2,\ldots ,k\}$ consists of n values $s_{i,j}$, $i \in \{1,2,\ldots ,n\}$, cf. Table 1.

Table 1. The solutions $s_1, ..., s_k$ of the sub-CSP $P_{sub}$

To define a deterministic finite automaton as the basis for the regular constraint, we need the set $T = \{T_1,\ldots ,T_n\}$ of prefix sets of all solutions of $P_{sub}$, where all elements in $T_i$ are concatenations of the i first values of a solution $s \in S$ (see Eq. 3):

$$\begin{aligned} T_i = \bigcup \limits _{l=1}^k \{s_{1,l} \ \circ \ s_{2,l} \ \circ \ \ldots \ \circ \ s_{i,l} \; | \; \forall i \in \{1,\ldots ,n\}\} \end{aligned}$$

(3)

This results in e.g. $T_1=\{s_{1,1}, s_{1,2}, \ldots , s_{1,k}\}$, $T_2 = \{s_{1,1} \circ s_{2,1}, s_{1,2} \circ s_{2,2}, \ldots , s_{1,k} \circ s_{2,k}\}$, $T_n = S$. Note that we enumerate the elements in each $T_i$ from 1 to k but actually they mostly have fewer elements then k for the reason that multiple occurrences of elements do not occur in sets. It follows $|T_1| \le |T_2| \le \ldots \le |T_n| = k$.

For each element t of each set $T_i,\ i \in \{1,\ldots ,n-1\}$ a state $q_{t}$ for the DFA is created, which represents the solution prefix t. Furthermore, the initial state $q_{start}$ and the final state $q_{end}$ (representing all solutions $S = T_n$ of $P_{sub}$) are added to Q. Thus, the set of states Q of the DFA is

$$Q = \{q_{t}\ |\ t \in T_i, i \in \{1,2,\ldots ,n-1\}\} \cup \{q_{start},q_{end}\}.$$

The initial state is $q_{start}$ and $F= \{q_{end}\}$ is the set of final states.

The alphabet $\varSigma$ of the DFA is the union of all domains of the variables of $X'$:

$$\begin{aligned} \varSigma = \bigcup \limits _{D_i \in D'} D_i \end{aligned}$$

(4)

Finally, we define the transition function $\delta$ as follows:

• Let $t \in T_{1}$. Then it holds

  $$\begin{aligned} \delta (q_{start},t) = q_t \end{aligned}$$

  (5)

• Let $t_{i-1}$ be an element in $T_{i-1}$, $t_{i}$ be an element in $T_{i}$, $i \in \{2,\ldots , n-1\}$ and $w \in D_i$ with $t_{i} = t_{i-1} \circ w$. Then it holds

  $$\begin{aligned} \delta (q_{t_{i-1}},w)=q_{t_i} \end{aligned}$$

  (6)

• Let $t_{n-1}$ be an element in $T_{n-1}$, $t_{n}$ be an element in $T_{n} = S$ and $w \in D_n$ with $t_{n} = t_{n-1} \circ w$. Then it holds

  $$\begin{aligned} \delta (q_{t_{n-1}},w)= q_{end} \end{aligned}$$

  (7)

This altogether provides the DFA $M = (Q, \varSigma , \delta , q_{start},\{q_{end}\})$. The constraint $regular(X', M)$ can be used as a replacement for the constraints of $C'$ in the original CSP P.

Remark 2

This algorithm is only useful for sub-CSPs $P_{sub}$ which are proper subsets of the original CSP P ($size(P_{sub}) \ll size(P)$). Solving a sub-problem $P_{sub}$ and finding all solutions is also an NP-hard problem. Nevertheless, due to the exponential growth of constraint problems, sub-problems with smaller size than the original problem can be solved significantly faster.

4 Examples and Experimental Results

After presenting our approach to transform the constraints of small sub-CPSs into a regular constraint, we want to show two case studies to underline its benefits. For this, we use the Black Hole Problem [17] and the Solitaire Battleships Problem [9] from the CSPlib.

All the experiments are set up on a DELL laptop with an Intel i7-4610M CPU, 3.00 GHz, with 16 GB 1600 MHz DDR3 and running under Windows 7 professional with service pack 1. The algorithms are implemented in Java under JDK version 1.8.0_191 and Choco Solver [20]. We used the DowOverWDeg search strategy which is explained in [5] and is used as default search strategy in the Choco Solver [20].

4.1 The Black Hole Problem

Black Hole is a common card game, where all 52 cards are played one after the other from seventeen face-up fans of three cards into a discard pile named ‘black hole’, which contains at the beginning only the card $A\spadesuit$. All cards are visible at all times. A card can be played into the ‘black hole’ if it is adjacent in rank to the previous card (colors are not important). The goal is to play all cards into the Black Hole.

Black Hole was modelled for a variety of solvers by Gent et al. [10]. We use the simplest and most declarative model of Dekker et al. [8], where two variables a and b represent adjacent cards if $|a-b| \; mod \; 13 \in \{1,12\}$.

The heuristic Weak Propagation, presented in [1], detects the adjacency constraints as replaceable¹. For our benchmark suite we computed 50 different instances of the Black Hole Problem, where 49 instances are randomly created (so the position of every card in the 17 fans is random) and the remaining instance has an enumerated card distribution ($1\spadesuit$, $2\spadesuit$, ..., $K\spadesuit$, $A\clubsuit$, $1\clubsuit$,..., $K\clubsuit$, $A\heartsuit$, $1\heartsuit$, ..., $K\heartsuit$, $A\diamondsuit$, $1\diamondsuit$, ..., $K\diamondsuit$).

For all instances, we limited the solution time to 10 min and each problem was solved in 4 ways:

• 1. Original: The problem was modelled as described in [8].

• 2. Table: The detected adjacency constraints were substituted by table constraints.

• 3. Regular: The detected adjacency constraints were substituted by regular constraints.

• 4. RegularIntersected: The detected adjacency constraints were substituted by only one regular constraint. The single regular constraint was created by the intersection of the underlying automatons of the substituted regular constraints from item (3) Regular as given above.

Fig. 1.

The time improvements (in %) of the Table, Regular and RegularIntersected models for finding the first solution of each instance of the Black Hole Problem in comparison to the Original model (0%).

Table 2. Overview of the Black Hole benchmark.

Figure 1 shows the time improvements (in %) of the three substituted models (Table, Regular and RegularIntersected) in comparison to the Original model when the first solution is searched. In 49 of 50 cases all modified models are better than the original. The only exception is sample case 8, where the original approach is 62–95% faster than the substituted ones². Table 2 shows that the Table approach was 25 times, the RegularIntersected approach was 19 times, the Regular approach was two times and the Original approach was one time the fastest. In average we could reach the first solution $83.413\%$, $82.054\%$ or $84.165\%$ faster than the Original approach and we could solve many more problem instances with the substitution approaches in the time limit in comparison to the Original model (47 instead of 7).

4.2 The Solitaire Battleships Problem

The Solitaire Battleships Problem is a famous symbol puzzle, where several ships with different sizes must be placed on a two-dimensional grid. The ships may be oriented horizontally or vertically, and no two ships will occupy adjacent grid squares, not even diagonally. Numerical values along the right hand side of and below the grid indicate the number of grid squares in the corresponding rows and columns that are occupied by vessels (see more details in [9]).

We created an equivalent Choco version of the MiniZinc model given in [9] and tested the introductory example and the 35 instances given in the “sb_Mini-Zinc_Benchmarks.zip” from [9]. We indicated the “spacing constraints”, the “ship shape constraints” and the “count number of bigger ships constraints” as potential good candidates for a substitution by regular (or table) constraints.

For all instances we limited the solution time to 30 min and each problem was solved in five ways:

• 1. Original: The problem was modelled as described in [9].

• 2. Table: With reference to [9], the single lines 75 to 80 of the “spacing constraints”, the single lines 86 to 89 and the three lines 91 to 93 together of the “ship shape constraints” and each two lines 117 to 118 and 122 to 123 together of the “count number of bigger ships constraints” were each substituted by singleton table constraints.

• 3. Regular: The lines enumerated in Table were substituted with regular constraints.

• 4. RegularIntersected: Equivalently to Regular, except the partial constraints in “count number of bigger ships constraints” which count the number of ships of size s in a row, respectively in a column, were combined each to one regular constraint.

• 5. TableRegularIntersected: There, we have the same combined regular constraints (for representing the “count number of bigger ships constraints”) as described in RegularIntersected, but, apart from that, use the table constraints described in Table (for representing the “spacing constraints” and “ship shape constraints”).

Figure 2 shows that the results for the Solitaire Battleships Problem are not that clear as the results for the Black Hole Problem. A look into Table 3 reveals that the improvements for finding a first solution are very streaky. The Table approach was the best approach, if using only one substitution style (tabulation or regularization). It found the first solution in 9 cases as fastest and was in average 37% faster than the original approach. The Regular approach slows the solution process down here but the RegularIntersected approach leads again to a speed up (2 times fastest approach, 29.701% better as the Original approach), which is not much worse than the speed up from the Table approach.

Fig. 2.

The time improvements (in %) of the Table, Regular, RegularIntersected and TableRegularIntersected models for finding the first solution of each instance of the Solitaire Battleships Problem in comparison to the Original model (0%).

Table 3. Overview of the Black Hole benchmark.

The TableRegularIntersected approach shows that a combination of regularization and tabulation can lead to a significant improvement. Here it was the best approach. It could solve the most problems (30), could find most often as fastest the first solution (19) and had in average the biggest time improvement (60.763%).

Remark 3

The TableRegularIntersected approach was not calculated fully automatically here, but it shows the potential of both approaches in combination. Future work has to be done automate the combination of both approaches.

Remark 4

In the evaluation, we did not present the needed time for the trans- formations. Depending on the specific CSPs, we observed big differences in the necessary transformation times. In our case, the total transformation time needed for all transformations were in all Black Hole instances less than three and in all Solitaire Battleship instances less than four seconds. Because the transformation time can be neglected in comparison to the solution time (less than three respectively four seconds vs. 10 respectively 30 min) we did not figure out them explicitly.

5 Conclusion and Future Work

We presented a new approach for the optimization of general CSPs using the regular constraint. For this a suitable sub-set of constraints are detected (for example with heuristics presented in [1]), solved separately and transformed into a regular constraint. Two benchmarks stress the benefit of this approach in comparison to the original problems and the competitiveness to the tabulation approach presented in [15]. Furthermore, our benchmarks indicate the potential of a combination of both approaches.

In the future we will research heuristics, for finding sub-CSPs which are especially suitable for the regularization approach. Besides, we want to consider the idea of direct transformations from several global constraints to equivalent regular constraints [4] and the combination of regular constraints transformed from global constraints with regular constraints transformed from sub-CSPs. We expect that this combination approach can be applied more often than the tabulation approach [15], because big sub-CSPs can be represented by a small DFA often; in contrast to this a table constraint always needs to store all solution tuples. Therefore, the regularization approach looks more promissing for big problems.

The most obvious next step is a detailed comparison of the regularization approach with the tabulation approach and the formulation of heuristics which suggest when which approach is more advantageous.