MiniCP: a lightweight solver for constraint programming

Abstract

This paper introduces MiniCP, a lightweight, open-source solver for constraint programming. MiniCP is motivated by educational purposes and the desire to provide the core implementation of a constraint-programming solver for students in computer science and industrial engineering. The design of MiniCP provides a one-to-one mapping between the theoretical and implementation concepts and its compositional abstractions favor extensibility and flexibility. MiniCP obviously does not support all available constraint-programming features and implementation techniques, but these could be implemented as future extensions or exploratory projects. MiniCP also comes with a full set of exercises, unit tests, and development projects.

1 Introduction

Motivation Logic-programming was the cradle of constraint programming [1,2,3] community is the mid-1980s. It is now used in numerous commercial applications, primarily in the areas of scheduling, routing, and timetabling, and is often hybridized with mathematical programming through decomposition techniques such as logical Benders decomposition and column generation. It is supported by several commercial solvers (e.g., CP Optimizer, an IBM product) and a multitude of open-source solvers. An interesting review of scheduling applications of CP Optimizer can be found in [4].

Yet, many undergraduate students in computer science and industrial engineering graduate without knowledge of constraint programming. The primary reason is simple: Constraint programming is simply not taught in most universities and there is a lack of high-quality teaching material in the community. Exacerbating this situation is the fact that most constraint-programming solvers have been built for speed and functionality, not for education purposes. As a result, they are often hard to penetrate and modify, and are not particularly well-adapted for use in the classroom. It is often the case that core concepts are hard to isolate among the wide variety of optimizations and features. This should be contrasted to the MiniSat solver for Boolean satisfiability which has largely contributed to the dissemination of (CDCL) SAT solvers. MiniSat has a neat, minimalist, and well-documented architecture that has enabled several generations of students and researchers to enter the field and make significant contributions.

This work is an attempt to bridge this gap: It introduces MiniCP, a light, open-source constraint-programming solver whose primary goal is to foster education in constraint programming. The hope is that MiniCP provides the core material to support classes in constraint programming at any institution with minimal effort. Not only does the MiniCP project contribute a minimalist and neat constraint-programming kernel; It also provides exercises, unit tests, and development projects. Ultimately, this educational solver will be accompanied by slides and video lectures that could be used for flipped offerings.

The Design and Implementation of MiniCP A key design decision in MiniCP is the one-to-one mapping between the theoretical foundations of constraint programming and the solver architecture. The existence of this mapping fundamentally simplifies the understanding of the implementation. The second design decision in MiniCP is the focus on extensibility and compositionality: It is reasonably simple to add new features to MiniCP and the interactions between these features are limited. The organization of this paper reflects these design decisions. The paper starts with a review of the foundations of constraint programming before focusing on its two main components: filtering and search. This is followed by a presentation of some more advanced features in filtering and search.

It is important to emphasize that MiniCP does not attempt to cover every aspect of constraint programming: This would defeat the purpose of this endeavor. Topics such as model reformulation and transformation, parallelization, richer variable types, e.g., set or continuous variables, learning-based constraint-programming solvers, copy-based solvers, soft constraints, and MDD-based approaches to name only a few are not discussed in this paper. This does not mean that they cannot be supported in MiniCP. Rather these topics could be the subject of future extensions or exploratory projects.

Table 1 MiniCP packages and their lines of codes (LOC) (computed with sloccount)

MiniCP is implemented in Java 8 to make it accessible to a large audience. The code makes extensive use of closures introduced in Java 8 through the concept of functional interfaces. “Appendix 1” contains a review of Java closures for completeness. Although the focus in MiniCP has been on simplicity and clarity (see Table 1 for its size), its performance is reasonable. “Appendix B” provides some benchmark results to substantiate this statement.

Influences The design of MiniCP is primarily influenced by the constraint-programming systems cc(fd) [5], Comet [6, 7], Objective-CP [8], and OscaR [9]. Some inspiration also came from the microkernel architecture introduced in [10]. Other solvers sharing similar designs are CP Optimizer [4], OR-Tools [11], Jacop [12], Mistral [13] and CHOCO [14]. Most of the implementation techniques in MiniCP were introduced in the constraint-programming system CHIP [3, 15]. For brevity, the presentation only provides references when this is not the case. Readers can also consult the chapter on implementation in the handbook of constraint programming [16].

Outline The rest of this paper is organized as follows. Section 2 reviews the foundations of constraint programming and Sect. 3 provides a preview of MiniCP through three running examples. Section 4 covers the filtering component of constraints and Sect. 5 its search component. Sections 6 and 7 consider some advanced filtering and search functionalities. Section 8 discusses the teaching material and Sect. 9 concludes the paper.

2 Foundations of constraint programming

This section presents the foundations of MiniCP. It covers, at a high-level level of abstraction, key concepts of constraint programming that will be refined in the actual implementation of MiniCP. Section 2.1 defines constraint satisfaction problems, the class of problems addressed by constraint-programming solvers. Section 2.2 then introduces filtering algorithms, the fundamental computational building block of constraint programming. Section 2.3 specifies and shows how to implement constraint propagation in terms of filtering algorithms. Section 2.4 proposes the concept of branching scheme that forms the basis of the search component of MiniCP. Finally, Sect. 2.5 specifies the search algorithm implemented in the MiniCP solver.

2.1 Constraint satisfaction problems

Constraint programming systems are tools to solve constraint satisfaction problems. A constraint satisfaction problem (CSP) is defined in terms of variables, domains, and constraints. This section formalizes these concepts which form the core of the MiniCP solver. Many generalizations are possible and some are discussed later in the paper.

Definition 1

(Domain) A domain is a finite set of discrete values in $\mathbb {Z}$.

Domains are denoted by the letter ${\mathcal {D}}$ and their values by the letter v. Domains support a variety of operations including membership ($v \in {\mathcal {D}}$), lower bound ($\min ({\mathcal {D}}) = \min _{v \in {\mathcal {D}}} v$), and upper bound ($\max ({\mathcal {D}}) = \max _{v \in {\mathcal {D}}} v$). Domains inherit the total ordering of $\mathbb {Z}$.

Definition 2

(Decision variable) A decision variable x is associated with a domain ${\mathcal {D}}$. It is instantiated (bound) if $|{\mathcal {D}}|=1$.

Definition 3

(Constraint) A constraint c is a relation defined over a set of decision variables. $Vars (c)$ denotes the variables of constraint c.

Definition 4

(CSP) A CSP is a triplet $\langle X,{\mathcal {D}},C\rangle$ where X is a set of decision variables, ${\mathcal {D}}$ is the Cartesian product of their domains, and C is a set of constraints defined over subsets of X. The domain of a decision variable x is denoted by ${\mathcal {D}}(x)$. Note that ${\mathcal {D}}= {\mathcal {D}}(x_0) \times \cdots \times {\mathcal {D}}(x_{n-1})$ when $X = \{x_0,\ldots ,x_{n-1}\}$.

Solving a CSP amounts to assigning the decision variables to values in their domains so that all constraints are satisfied. For simplicity, the presentation often assumes an underlying CSP $\langle X,{\mathcal {D}},C\rangle$ and refers to ${\mathcal {D}}$ as the domain of the CSP. Given two domains ${\mathcal {D}}_1$ and ${\mathcal {D}}_2$ over the same variables $\{x_0,\ldots ,x_{n-1}\}$, the intersection ${\mathcal {D}}_1 \cap {\mathcal {D}}_2$ is defined as ${\mathcal {D}}_1(x_0) \cap {\mathcal {D}}_2(x_0) \times \cdots \times {\mathcal {D}}_1(x_{n-1}) \cap {\mathcal {D}}_2(x_{n-1})$.

Definition 5

(Candidate solution) A candidate solution $\sigma$ assigns to each decision variable x a value in its domain, i.e., $\sigma (x) \in {\mathcal {D}}(x)$.

Definition 6

(Constraint valuation) The valuation of a constraint c with respect to a candidate solution $\sigma$ is the Boolean value $c(\sigma )$ which stands for $c(\sigma (x_0),\ldots ,\sigma (x_{n-1}))$ where $Vars (c) = \{x_0,\ldots ,x_{n-1}\}$.

Definition 7

(Solution) A solution $\sigma$ to a CSP $\langle X,{\mathcal {D}},C\rangle$ is a candidate solution that satisfies all constraints, i.e., $\forall c \in C: c(\sigma ).$ The set of solutions to a CSP $\langle X,{\mathcal {D}},C \rangle$ is denoted by $\mathcal{S}(\langle X,{\mathcal {D}},C\rangle )$.

Note that a solution to a CSP can also be viewed as a domain ${\mathcal {D}}$ that binds all variables, i.e., $|{\mathcal {D}}(x)| = 1$ for every variable x. These concepts can also be generalized to the case where an objective function must be minimized (or maximized).

Definition 8

(COP) A constraint optimization problem (COP) is a quadruplet $\langle X,{\mathcal {D}},C,f\rangle$ in which f is a real function over a subset of variables $Vars (f) \subset X$.

Definition 9

(Function valuation) The valuation of a function f with respect to a candidate solution $\sigma$ is the value $f(\sigma )$ which stands for

$$\begin{aligned} f(\sigma (x_0),\ldots ,\sigma (x_{n-1})) \end{aligned}$$

where $Vars (f) = \{x_0,\ldots x_{n-1}\}$.

Definition 10

(Optimal solution) An optimal solution to $\langle X,{\mathcal {D}},C,f\rangle$ is a solution $\sigma ^*$ such that $\forall \sigma \in \mathcal{S}(\langle X,{\mathcal {D}},C\rangle ): f(\sigma ^*) \le f(\sigma ).$

2.2 Filtering algorithms

Filtering algorithms are the cornerstone of constraint programming. Their goal is to prune values from the variable domains without removing any solutions. Each constraint is associated with a filtering algorithm which receives domains for the constraint variables as input and returns new domains.

Definition 11

(Filtering algorithm) A filtering algorithm $\mathcal{F}_c$ for a constraint c is a function from domain to domain satisfying

$$\begin{aligned} \forall {\mathcal {D}}: \mathcal{F}_c({\mathcal {D}}) \subseteq {\mathcal {D}}\; \wedge \; \mathcal{S}(\langle Vars (c), {\mathcal {D}}, \{c\} \rangle ) = \mathcal{S}(\langle Vars (c), \mathcal{F}_c({\mathcal {D}}), \{c\} \rangle ). \end{aligned}$$

A filtering operator $\mathcal{F}_c$ is monotone if ${\mathcal {D}}_1 \subseteq {\mathcal {D}}_2 \Rightarrow \mathcal{F}_c({\mathcal {D}}_1) \subseteq \mathcal{F}_c({\mathcal {D}}_2)$.

Constraint-programming solvers typically aim at enforcing some strong consistency properties on the output of a filtering algorithm. Bound and domain consistency are two such desirable properties. Bound consistency requires that, after filtering, the bounds of every variable belong to a solution of the constraint assuming interval domains. Domain consistency requires that, after filtering, each value in the variable domains belong to a solution of the constraint. Domain consistency is the strongest property that can be enforced by a filtering algorithm when considering only one constraint at a time, and when restricted to pruning domain values only.

Definition 12

(Bound consistency) A constraint c ranging over variables $Vars (c)=\{x_0,\ldots ,x_{n-1}\}$ is bound-consistent wrt ${\mathcal {D}}$ if and only if, for every $i \in 0\ldots n-1$, there exist values

$$\begin{aligned} v_j \in \{\min ({\mathcal {D}}(x_j)),\ldots ,\max ({\mathcal {D}}(x_j))\} \,\,\, (0 \le j <n\,:\, j \ne i) \end{aligned}$$

such that

$$\begin{aligned} \begin{array}{lc} c(v_0,\ldots ,v_{i-1},\min ({\mathcal {D}}(x_i)),v_{i+1},\ldots ,v_{n-1}) &{} \wedge \\ c(v_0,\ldots ,v_{i-1},\max ({\mathcal {D}}(x_i)),v_{i+1},\ldots ,v_{n-1}) &{} \end{array} \end{aligned}$$

holds.

Definition 13

(Domain consistency) A constraint c ranging over variables $Vars (c) = \{x_0,\ldots ,x_{n-1}\}$ is domain-consistent wrt ${\mathcal {D}}$ if and only if, for every $i \in 0\ldots n-1$ and every value $v_i \in {\mathcal {D}}(x_i)$, there exist values $v_j \in {\mathcal {D}}(x_j)$ ($0 \le j < n: j \ne i$) such that $c(v_0,\ldots ,v_{i-1},v_i,v_{i+1},\ldots ,v_{n-1})$ holds.

Definition 14

(Consistent filtering algorithm) A filtering algorithm $\mathcal{F}_c$ for a constraint c is bound-consistent (resp. domain-consistent) if, for all domain ${\mathcal {D}}$, c is bound-consistent (resp. domain-consistent) wrt $\mathcal{F}_c({\mathcal {D}})$.

Example 1

(Bound-consistent filtering algorithm of $x = y + 1$) Consider a constraint c of the form $x = y + 1$. A bound-consistent filtering algorithm returns the domains

$$\begin{aligned} \begin{array}{l} {\mathcal {F}}_c({\mathcal {D}})(x) = \{ v \in {\mathcal {D}}(x): \min ({\mathcal {D}}(y)) + 1 \le v \le \max ({\mathcal {D}}(y)) + 1 \}, \\ {\mathcal {F}}_c({\mathcal {D}})(y) = \{ v \in {\mathcal {D}}(y): \min ({\mathcal {D}}(x)) - 1 \le v \le \max ({\mathcal {D}}(x)) - 1 \}. \end{array} \end{aligned}$$

Example 2

(Domain-consistent filtering algorithm of $x = y + 1$) Consider a constraint c of the form $x = y + 1$. A domain-consistent filtering algorithm returns the domains

$$\begin{aligned} \begin{array}{l} {\mathcal {F}}_c({\mathcal {D}})(x) = \{ v \in {\mathcal {D}}(x): v-1 \in {\mathcal {D}}(y)\}, \\ {\mathcal {F}}_c({\mathcal {D}})(y) = \{ v \in {\mathcal {D}}(y): v+1 \in {\mathcal {D}}(x)\}. \end{array} \end{aligned}$$

It is useful to point that, while the domain-consistent filtering algorithm must be applied each time a value is pruned from the domain of x or y, this is not the case for the bound-consistent version. Indeed, for enforcing bound consistency, it suffices to apply the filtering when the bounds of x or y are updated. MiniCP implements this optimization by associating dedicated lists of constraints with variables as discussed in Sect. 4.3.

2.3 Constraint propagation

The core of a constraint-programming solver is a propagation algorithm that applies filtering algorithms until no more values can be pruned from the variable domains. Algorithm 1 depicts the most basic constraint-propagation algorithm: It simply iterates the application of the filtering algorithm associated with each constraint until none of them reduces the domains. More formally, Algorithm 1 computes the greatest fixpoint of the operator $\mathcal{F}_C = \bigcap _{c \in C} \mathcal{F}_c({\mathcal {D}}).$ In other words, given a CSP $\langle X, {\mathcal {D}}, C\rangle$, the constraint propagation ${\mathcal {F}}$ returns a domain ${\mathcal {D}}^*$ defined by

$$\begin{aligned} {\mathcal {D}}^* = \max \{{\mathcal {D}}^p \subseteq {\mathcal {D}}: {\mathcal {D}}^p = \mathcal{F}_C({\mathcal {D}})\}. \end{aligned}$$

(1)

When the filtering algorithms are monotone, this greatest fixpoint is unique and hence the order in which the filters are applied has no impact on the results. The constraint propagation can also be viewed as transforming a CSP $\langle X, {\mathcal {D}}, C\rangle$ into a CSP $\langle X, {\mathcal {D}}^*, C\rangle$ such that $\mathcal{S}(\langle X, {\mathcal {D}}, C\rangle ) = \mathcal{S}(\langle X, {\mathcal {D}}^*, C\rangle )$ and ${\mathcal {D}}^*$ satisfies Equation 1. If $|{\mathcal {D}}^*| = 0$, the CSP has no solution. If $|{\mathcal {D}}^*| = 1$, then ${\mathcal {D}}^*$ is a solution. Otherwise, no conclusion can be drawn. When $|{\mathcal {D}}^*| = 0$, we say that the constraint propagation fails or is a failure. When $|{\mathcal {D}}^*| = 1$, we say that the propagation succeeds or is a success.

Algorithm 1 is rather naive as it applies all filtering algorithms each time the domain of a variable is pruned. In practice, constraint-programming solvers only reconsider the filtering algorithms for constraints whose variables have seen their domains reduced. This is captured in Algorithm 2 which is organized around a queue of constraints. Initially, the queue Q contains all constraints and each iteration pops a constraint from Q and applies its filtering algorithm. It then enqueues all constraints that have at least one variable whose domain has been pruned. The algorithm terminates when the queue is empty.¹ The MiniCP implementation goes one step further by also avoiding to enqueue constraints whose filtering algorithms will not prune the domains as discussed earlier. This is covered in detail in Sect. 4.3 where it is shown that each variable is associated with several lists of constraints.

2.4 Branching

Constraint propagation may fail, succeed, or be inconclusive. In the last case, to make further progress, constraint-programming solvers typically partition the CSP into a set of simpler CSPs. Some solvers offer substantial flexibility to express how to branch, while others do not give any control to users. MiniCP uses the concept of branching scheme to express the decomposition process.

Definition 15

(Branching scheme) A branching scheme for $\langle X,{\mathcal {D}},C\rangle$ is a set of CSPs $\{\langle X,{\mathcal {D}},C \cup \{c_0\} \rangle$,...,$\langle X,{\mathcal {D}},C \cup \{c_{k-1}\} \rangle \}$ such that

$$\begin{aligned} {\mathcal {S}}(\langle X,{\mathcal {D}},C\rangle ) = \bigcup _{i \in 0\ldots k-1} {\mathcal {S}}(\langle X,{\mathcal {D}},C \cup \{c_i\}\rangle ) \end{aligned}$$

and, for all i, j with $0 \le i< j < k$,

$$\begin{aligned} |{\mathcal {S}}(\langle X,{\mathcal {D}},C \cup \{c_i\}\rangle ) \cap {\mathcal {S}}(\langle X,{\mathcal {D}},C \cup \{c_j\}\rangle )| = 0. \end{aligned}$$

Note that, to specify a branching scheme, it suffices to specify the constraints $\{c_0,\ldots ,c_{k-1}\}$.

Example 3

(Minimum value branching) The minimum value branching selects a free variable $x \in X$ and uses two constraints: $x = \min ({\mathcal {D}}(x))$ and $x \ne \min ({\mathcal {D}}(x))$.

Example 4

(Dichotomic value branching) The dichotomic value branching selects a free variable $x \in X$ and uses two constraints: $x \le \mathrm {mid}({\mathcal {D}}(x))$ and $x > \mathrm {mid}({\mathcal {D}}(x))$, where $\mathrm {mid}({\mathcal {D}})$ is the mid-point value in ${\mathcal {D}}$.

2.5 Search

It is now possible to specify the search algorithm underlying MiniCP as a simple recursive algorithm implementing a depth-first search with chronological backtracking. Procedure CPSearch is depicted in Algorithm 3; It takes a CSP as input and returns its solutions. The algorithm first performs constraint propagation (line 1). If the propagation fails, the algorithm returns no solution (lines 2–3). If the propagation succeeds, it returns the solution (lines 4–5). Otherwise, the algorithm applies the branching scheme to obtain a set of constraints (line 7). The resulting CSPs are solved recursively and the algorithm returns the union of their solutions. The main difference between this abstract version and the actual implementation in MiniCP is the way the domains and the constraints are updated which is discussed in Sect. 4.4.

Note that MiniCP solves optimization problems as a sequence of feasibility problems. Each time a solution with objective value $f^*$ is found, MiniCP searches for a feasible solution whose objective improves upon $f^*$. The actual implementation, which also avoids redundant computations, is discussed in Sect. 5.4.

3 A preview of MiniCP

This section presents three simple MiniCP programs. Their main purpose is to provide a clear link between the theoretical foundations and the implementation. These programs will introduce the concrete counterparts to the abstract concepts presented in Sect. 2: The decision variables, the domains, the constraints, the branching scheme, and the search. Although these constraint programs are relatively simple, they convey the essence of MiniCP and its implementation. More sophisticated techniques are presented later in the paper. Curious readers can refer to the source code repository to check out the version tagged 1.0.1 and consult the files NQueensPaper.java, MagicSeriePaper.java and QAPPaper.java to see the actual code with all the necessary Java details (e.g., import statements).

3.1 The N-Queens problem

The first MiniCP program solves the classic queens problem which amounts to placing n queens on an $n\times n$ checkerboard so that no two queens can attack each other, i.e., no two queens are on the same row, column, or diagonals.

The MiniCP model uses a simple encoding that associates a decision variable $q_i$ with each column $i \in \{0,\ldots ,n-1\}$ to represent the row of the queen placed in this column. By virtue of the encoding, it is only necessary to impose constraints that ensure that no queens are on the same row and diagonals, which can be expressed as

$$\begin{aligned} \begin{array}{lcl} \forall \, i,j \in 0\ldots n-1 \wedge i< j &{}:&{} q_i \ne q_j \\ \forall \, i,j \in 0\ldots n-1 \wedge i< j &{}:&{} q_i-i \ne q_j - j \\ \forall \, i,j \in 0\ldots n-1 \wedge i < j &{}:&{} q_i+i \ne q_j + j \\ \end{array} \end{aligned}$$

The MiniCP program is presented in Listing 1 and contains three main parts: the declaration of the decision variables (line 3), the constraint specification (lines 5–10), and the branching scheme (lines 12–28). Line 2 creates a CP solver cp and line 3 creates the array q of n decision variables, each with a domain $\{0\ldots n-1\}$. Lines 5–10 create the binary disequations and post them to the CP solver. A disequation such as $q_i + i \ne q_j + j$ boils down to $q_i \ne q_j + (j - i)$ which is a binary notEqual constraint $x \ne y + v$ since $q_i$ and $q_j$ are two variables and $j-i$ is a constant.

The branching scheme in lines 12–28) is given as a closure (see “Appendix A” for a review of Java closures) that will be applied repeatedly during the search as specified in Algorithm 3. The branching has two main parts: the selection of the variable to assign (lines 13–18) and the creation of the branching constraints (lines 19–27). The variable selection is extremely simple: The first free variable is selected. The code simply iterates over all variables in the array and computes the index idx of this free variable. More complicated variable selections (e.g., selecting the free variable with the smallest domain) can be easily implemented in a similar way. The remaining of the branching scheme generates branching constraints that are represented as an array of procedures (i.e., void to void closures). If all variables are bound, then the branching scheme returns an empty array (line 20) to notify the search it is a solution. Otherwise, the code implements the minimum value branching specified in Example 3. In Lines 24–25, the branching scheme defines two closures which will create the branching constraints when called and these closures are inserted in the array of branching decisions in line 26. The branching scheme is passed as a parameter to a depth-first search object in Line 12. The depth-first search is performed during the solve call in line 32 and computes all solutions. To print the solution, it suffices to use the block in lines 29-31 that specify a closure to execute each time the solver produces a solution.

The binary disequations in lines 5–10 can be replaced by three global constraints:

Global constraints are a fundamental concept in constraint programming as they enable to capture substructures arising in many applications. These global constraints can then be associated with dedicated filtering algorithms that exploits the properties of these substructures. In the queens problem, the global constraints express that a collection of variables must take different values. For instance, Line 3 specifies that all variables in array q must take different values. Line 4 above deserves some explanations. The sub-expression

makes use of the function

which creates an array of size n whose variables are obtained using the closure parameter body. In the above, the function Factory.minus(q[i],i) returns an integer variable, say x[i], whose values are subject to the constraint x[i] = q[i] - i. As a result, the second allDifferent constraint specifies that the expressions $q_i - i$ ($0 \le i < n$) evaluate to different values.

The MiniCP code heavily uses the factory design pattern [18] to create solvers, variables, and constraints using static methods (e.g., makeSolver, makeIntVarArray, sum, isEqual, mul, makeDfs) of the Factory class. It is possible to use the Java import static instruction to make the factory calls implicit as illustrated in the next MiniCP example.

3.2 The magic series problem

A series $S=(s_0,s_1,\ldots ,s_{n-1})$ is magic if $s_i$ represents the number of occurrences of i in S. Listing 2 gives a MiniCP program for finding magic series. The core of the MiniCP model is the constraints

$$\begin{aligned} \sum _{j=0}^{n-1} \mathbb {1}(s_j = i) = s_i \;\;\;\; (0 \le i < n) \end{aligned}$$

where $\mathbb {1}$ denotes the indicator function. The last two constraints,

$$\begin{aligned} \sum _{j=0}^{n-1} s_j = n \end{aligned}$$

and

$$\begin{aligned} \sum _{j=0}^{n-1} j \times s_j = n \end{aligned}$$

express properties of magic series and help reduce the search space.

The MiniCP program is a direct encoding of these constraints. It makes use of the sum(a,s) constraint that holds if the elements in array a sum to s. It also uses the isEqual(x,v) indicator function that returns a 0-1 variable whose value is 1 if x is equal to v and 0 otherwise. The use of indicator functions is often called reification in constraint programming and is explained in Sect. 6. The declaration of a local variable fi set to i on line 8 is the consequence of a Java idiosyncrasy that precludes the use of i in the closure on the following line as it gets modified through subsequent iterations.

The impact of the last two constraints is significant: Without them, the search for a magic series of length 200 requires 32,430 choices. With them, only 400 choices are needed.

3.3 A quadratic assignment problem

This section considers an assignment problem where a set of n facilities must be assigned to n different locations. The distance between two locations l and m is given by $d_{l,m}$ and each pair of facilities (i, j) is associated with a weight $w_{i,j}$. The goal of the assignment is to minimize the sum of the weighted distances between the locations of each pair of facilities.

$$\begin{aligned} \sum _{i=0}^{n-1} \sum _{j=0}^{n-1} d_{x_i,x_j} \cdot w_{i,j} \end{aligned}$$

The model is given in Listing 3. It assumes the presence of two inputs: matrix w that specifies the weights and matrix d that specifies the distances. It makes use of the element constraint [19] that allows decision variables to index arrays and matrices and whose implementation is discussed in Sect. 6.4. More specifically, element(d,x[i],x[j]) returns a variable whose value is equal to the expression d[x[i]][x[j]].

To build the objective function, the MiniCP program creates an auxiliary variable dij for the distance between two facilities i and j in the loop spanning lines 7–11. The same loop also accumulates in array weightedDist all the weighted distance. Lines 12–13 then specify the objective as the minimization of the sum of the weighted distances (the sum is held in a variable totCost).

4 The constraint propagation implementation

This section describes the MiniCP implementation of constraint propagation. Section 4.2 proposes one possible implementation for domains and Sect. 4.3 describes the implementation of variables. Section 4.4 discusses how to implement constraints and Sect. 4.5 depicts the constraint-propagation algorithms. Since many of these concepts refer to each other, the section starts with a number of interfaces.

4.1 Interfaces

The Variable Interface The interface for integer variables is given in Listing 4 and offers three classes of methods. First, it provides a number of accessors to query the variable domain. Second, it offers a number of mutators to reduce the variable domain (i.e., removing a value, assigning a value, removing values below a certain threshold, and removing values above a certain threshold). Finally, it provides a number of methods to link variables and constraints. More specifically, method propagateOnDomainChange(c) specifies that constraint c must be propagated each time the domain of the variable is updated, method propagateOnBoundChange(c) specifies that constraint c must be propagated each time one of its bounds is updated, and method propagateOnBind(c) indicates that constraint c must be propagated when the variable is bound.

The Constraint Interface The constraint interface is given in Listing 5. The main methods are post and propagate. Method post is called once when the constraint is added to the MiniCP solver. It typically initializes internal data structures, links variables and constraints, and performs the first propagation step. Method propagate is the core of the implementation: It applies the filtering algorithm of the constraint and is called repeatedly. The remaining methods are used for optimizing constraint propagation and are discussed in Sect. 4.5

The Objective Interface The objective interface is given in Listing 6. The sole method tighten is meant to be called when the solver produces a solution to a constraint optimization problem compelling the solver to produce a next solution whose quality strictly exceeds that of the incumbent. If the COP is a minimization problem, the tighten method would pickup the primal bound as value of the objective function and then impose the requirement that the objective should be strictly less than this new primal bound.

The Domain Interface The interface of domains is given in Listing 7. The first set of methods return the minimum and maximum values in the domain, the domain size, whether the variable is bound, and whether a value v belongs to the domain. The remaining four methods respectively remove, from the domain, value v, all values but v, all values smaller than v, and all value greater than v. These last four methods receive as argument a domain listener, whose interface is given in Listing 8, as proposed in [20]. A domain listener allows an (arbitrary) object to be notified of various events on the domain, namely, when the domain becomes empty (empty), when it has only one element (bind), when it has changed (change), or when its smallest (changeMin) or largest (changeMax) value has changed. As mentioned in Sect. 2.2, this information is useful to decide whether a constraint needs to be propagated after a domain update.

Solver Interface The Solver interface is shown in Listing 9. Method post is used to register constraints. The minimize and maximize methods are available to state an objective function. Method schedule is called to schedule a constraint for propagation and method fixPoint implements Algorithm 2. Method onFixPoint allows hooking up a procedure notified whenever a fixpoint is computed.

4.2 A domain implementation

This section proposes a domain implementation in terms of sparse sets [21]. The implementation of the domain is rather generic however and other set representations can easily be used instead.

Listing 10 presents the core of the domain implementation in terms of a sparse set. The constructor creates the sparse set and the domain accessors simply delegate to the sparse set. The remove method is more interesting: Its role is not only to delegate the removal to the sparse set but also to notify the domain listener about which domain events are arising due to the removal. Lines 13–14 test whether the minimum or maximum value is removed, and line 15 delegates the removal to the sparse set. The rest of the method simply places the proper calls on the domain listener: It calls empty if the domain becomes empty, changeMin and changeMax if the minimum or maximum values are removed, change if a value is removed, and bind if there is a single value left in the domain. The remaining methods for value removals can be implemented similarly.

It remains to present the sparse set implementation which represents subset of numbers between a lower bound L and an upper bound U. For simplicity, the presentation assumes that $L=0$: It is easy to add a shift factor to deal with the more general case. The sparse set uses two arrays, values and indices, and an integer size to track how many elements are in the set. Array values contains a permutation of the values 0..U, while array indices keeps track of the positions of the elements in array values. In other words, it holds that

$$\begin{aligned} \texttt {values}[\texttt {indices}[i]] = i. \end{aligned}$$

Fig. 1

A sparse set set of 9 values at initialization

Fig. 2

Sparse set after the removal of values 4 and 6

Figure 1 depicts the representation of set $\{0,\ldots ,8\}$ after initialization and Fig. 2 shows the representation when values 4 and 6 have been removed. Value 4 is removed by swapping its value in array values with the last element of the array, updating array indices appropriately, and decrementing size by one. Removing value 6 amounts to swapping 6 with the last present element of array values, i.e., 7, and updating the indices and size.

All the elements present in the set are between indices 0 and size-1. Finding out if an element is in the set takes constant time: It suffices to consult array indices and test whether its position is smaller than size. Removing a value also takes constant time as highlighted by the discussion above. Iterating over the elements of the set takes linear time in the number of elements in the set. Removing all values but v amounts to swapping v with the element in the first position, updating the entries in indexes to reflect the new positions, and updating size to 1. Removing all the values below (or above) a given threshold v take time $\mathcal{O}(|\Delta |)$ where $\Delta$ is the set of removed values: It suffices to apply the remove operation for each value that needs to be removed.

4.3 The variable implementation

Listing 11 presents the implementation of integer variables. The instance variables include a reference to the solver, a reference to the domain and three stacks of constraints based on the abstract data type StateStack (see Sect. 5.3 for details on this data structure). Each stack corresponds to an event type, specifying when the constraints must be scheduled for propagation. For instance, the onBind stack stores the constraints to be propagated when the variable is bound.

Lines 29–33 provide accessors to the variable dom, while lines 35–38 present the methods to remove values from the domain. Lines 40–42 describe methods to link constraints to the variable. The constructor creates the domain and the constraint stacks.

The remove methods are the most interesting aspect of the variable implementation. They delegate the removals to the domain, passing a domain listener as parameter. The methods of the listener are called depending upon what events are arising in the domain, e.g., method empty is called when the domain is empty and method change when the domain is updated. The implementation of the domain listener is shown in lines 8–14. Method empty throws an exception, indicating a failure of the propagation, which will be caught in the search implementation. The remaining methods simply schedule the relevant constraints for propagation. For instance, method bind schedules all constraints in the stack onBind.

Example 5

Consider a variable x with domain $\{1,2,3,4,5,6\}$ and the result of an invocation of the remove(int v) method on value 3. The computation can be summarized as follows.

• 1. The removal is delegated to its domain (line  35). The domain method receives the value to remove (3) and the domain listener.

• 2. The change method of the listener is called (line 11) and consequently all the constraints present in onDomain container are scheduled for propagation (method scheduleAll spanning lines 15–18).

If the initial domain is $\{3,4\}$, the domain would become a singleton $\{4\}$ and therefore the bind method of the listener would also be called to propagate the constraint in the onBind container. Finally, if the initial domain ${\mathcal {D}}(x)$ is the singleton $\{3\}$, the removal of 3 would make the domain empty, in which case the empty method of the listener would be called, which will throw an exception.

Observe how the domain listener modularizes the logic to react to domain events. By changing or upgrading the domain listener, it is possible to implement advanced features such as views.

4.4 The implementation of constraints

Constraints implement the interface in Listing 5 and subclass the abstract class AbstractConstraint shown in Listing 12. Class AbstractConstraint factorizes the implementation of methods that accelerate the fixpoint algorithm: These are discussed in Sect. 4.5. Subclasses override the post and propagate methods which are called when constraints are first posted to the solver and when constraints must be propagated respectively. During calls to post and propagate, exceptions of type InconsistencyException are raised each time a failure is encountered (e.g., a variable domain becomes empty). Since filtering algorithms exploit the semantics of constraints, it is easier to present examples to illustrate the implementation of constraints.

Example 6

($x \le y$) Consider the implementation of $x \le y$. The inference rules are

• 1. $\max ({\mathcal {D}}(x)) \leftarrow \min \{ \max ({\mathcal {D}}(x)),\max ({\mathcal {D}}(y)))\}$

• 2. $\min ({\mathcal {D}}(y)) \leftarrow \max \{ \min ({\mathcal {D}}(y)),\min ({\mathcal {D}}(x)))\}$

The constraint implementation is given in Listing 13. The post method registers the constraint and links it to x and y with boundChange events, since no filtering takes place when removing values in the middle of the domain. The propagate method implements the filtering. Line 16 implements a simple activation optimization. If the constraint trivially holds, i.e., if $\max ({\mathcal {D}}(x)) \le \min ({\mathcal {D}}(y))$, the constraint is disabled since no filtering will take place in subsequent computations.

Example 7

($x \ne y + v$) Consider the implementation shown in Listing 14 of $x \ne y + v$ where v is a constant in $\mathbb {Z}$. The constraint was used in the queens program (Listing 1). The post method performs a simple case analysis. If either x or y is already bound, it removes the corresponding value from the domain of the other variable. Otherwise, it links the constraint with the variables with bind events. The propagate is invoked when one of the variables becomes bound. It removes the corresponding value from the domain of the other variables or fails if that variable is bound to that value. Line 24 implements a simple activation optimization. Once the value of the other unbound variable has been removed the constraint trivially holds and is thus disabled since no filtering will take place in subsequent computations.

4.5 The implementation of constraint propagation

Class MiniCP in Listing 15 is the core of the constraint propagation and its fixpoint method implements Algorithm 2. The implementation is organized around a queue of constraints to propagate. Method post posts a constraint and performs constraint propagation. Method fixPoint (lines 13–23) pops constraints from the propagation queue and propagates them until the queue is empty or a failure occurs. In case of a failure, the exception is caught, the queue is emptied, and the exception is thrown again to communicate it to the search. The propagation makes sure that a constraint is not pushed in the queue if it is already in it, using the schedule methods of the constraints. More precisely, method schedule (lines 7–12) checks whether the constraint is already scheduled and method propagate(Constraint c) (lines 25 to 29) resets the scheduled flag before calling the propagation provided that the constraint has not been deactivated. The flag is also reset in case of failure.

Unlike Algorithm 2, the implementation does not copy the domains of the variables (e.g., like in line 5 of Algorithm 2) but modifies them in place. These domains will be restored during backtracking as discussed in Sect. 5.2.

5 The search implementation

This section describes how to implement Algorithm 3. Observe that Algorithm 3 does not prescribe any search strategy: Different ordering policies for its queue Q lead to distinct search strategies. The MiniCP implementation is based on depth-first search, which is typical for constraint programming and is memory-efficient.

The main topic of this section is state management, the rest of the implementation being direct. As mentioned in Sect. 4.5, constraint propagation in MiniCP updates variable domains in place. As a result, in a first approximation, the variable domains after each fixpoint represent the state of the computation. When branching, MiniCP should thus save these domains in order to restore them in case of a failure so that the next branch is performed on the proper state. The state management is completely separated from the search itself and encapsulated in a state manager class. It is also important to mention that the MiniCP implementation exploits the last-in/first-out nature of depth-first search to optimize state management. Other search explorations may not benefit from similar optimizations.

The rest of this section is organized as follows. Section 5.1 presents the depth-first search implementation. Section 5.2 describes the state management and gives two possible implementations based on copying and trailing. The trailing state management strategy can be viewed as a optimized lazy implementation of the copying strategy. Section 5.3 revisits the domain implementation.

5.1 The depth-first search implementation

Listing  17 depicts the implementation of depth-first search² using the state manager interface presented in Listing 16. The important method at this stage is method withNewState which, informally speaking, executes a closure in a new state which is a copy of the current state. The depth-first search receives as input a state manager and a branching scheme, i.e., a closure that returns an array of branches when called. Method solve executes the depth-first search with a new state. Method dfs is the core of the search and is similar to Algorithm 3. It first applies the branching scheme to obtain an array of branches. If the array is empty, it means, in all the examples previewed in this paper, that the variables are all bound and the search completes by notifying that a solution has been found. Otherwise, the search iterates over all branches. For each of them, it creates a new state, applies the branch, and performs a recursive call. The searches described in this paper use methods equal and notEqual and it is useful to look at their implementation as well. Listing 18 depicts the implementation of Method equal. The method first assigns value v to variable x and then calls the constraint propagation on the solver. This call is the connection between the search and propagation. Note also that, if the constraint propagation fails, an exception is caught and the state is restored for the next branch (lines 18–24 in Listing 17).

It is worthwhile mentioning one difference between Algorithm 3 and the implementation in Listing 17. Line 7 of Algorithm 3 is implemented by line 13 in Listing 17. But the implementation does not manipulate constraints directly. Rather it receives an array of closures that, when called, will apply these constraints.

5.2 State specification

The state in MiniCP is represented by classes implementing two interfaces, StateInt and StateBool, that encapsulate an integer and a Boolean respectively. These state variables are created by the state manager. For conciseness only StateInt implementation is discussed next. Listing 19 depicts the StateInt interface which supports setting a new value and accessing the current value. Listing 20 depicts its use and the intended behavior assuming an existing StateManager sm. The implementation of state managers exploits the fact MiniCP uses a LIFO strategy in its search procedures, which is obviously the case for depth-first search.

Copying State Management The simplest state-management strategy creates a backup of the state, saving the values of all the StateInt and StateBool instances for future restoration. Listing 21 illustrates this implementation. Lines 1–3 show the interface of a backup entry, which has only one capability: the ability to restore its previous value. The main class, Copier, implements the StateManager interface. Its internal state consists of two containers. First, variable store keeps track of all state objects ever created. Factory methods makeStateInt and makeStateBool add a reference to any object they create in this container, as shown in lines 38–42. Second, variable prior contains a stack of states which are saved by method saveState and restored by method restoreState. Method saveState creates an instance of the nested class Backup whose constructor saves a copy of every object in the state store. Method restore of this backup object restores the saved values. Note that the backup object also saves the size of store since state objects may be created during the search and the proper size must be restored. The state objects are created by methods makeStateInt and makeStateBool which return objects of type CopyInt and CopyBool. The code for CopyInt is shown in Listing 22. Its save method creates a backup entry which is an instance of the nested class CopyIntStateEntry. Method restore of the nested class exploits the fact that it can refer to the this object of the encapsulating class.

Trailing State Management Saving all state variables is typically wasteful as only a few state variables are modified during a propagation step. MiniCP, like most constraint-programming implementations, uses a technique called trailing to lazily copy the state. In other words, trailing only copies the variables that are actually modified. The trailing mechanism described in this section was first implemented in constraint programming by the CHIP system [3, 15]. Knuth [22] attributes the first formulation of trailing and its usage in a backtracking algorithm to Floyd [23].

Listings 23 presents an implementation of the trail. Saving a state (method saveState) simply pushes the current backup on top of the backup stack (prior) (in constant time) and creates a new empty backup for the next batch of changes. Similarly, restoring the state (method restoreState) instructs the current backup to restore all changes that were tracked since the last call to saveState and then reinstates the previous backup from the prior stack. Lazily saving changes made to the state is the responsibility of the state objects. Those are created from the factory methods makeStateInt and makeStateBool which return, respectively, an instance of TrailInt or TrailBool.

Consider the implementation of TrailInt shown in Listing 24. The big difference with the Copier is that now the saving is lazy as it only happens when modification is performed on an object and untouched objects are never backed up. The TrailInt class implements the StateInt interface and is a cousin of CopyInt. Its mutator method setValue is at the core of the implementation. If the new value differs from the current value, it first trails (i.e., it backs up) the old value on the trail with an instance of the nested class StateEntryInt and then modifies its attribute v.

The implementation features a simple optimization that avoids trailing an object again if it has already been saved in the current backup. This is done by using an integer identifying the current backup (the magic attribute of the trail) and saving, inside the TrailInt instance, the magic value when the object is trailed. The magic attribute is incremented every time a backup is saved and restored.

Figure 3 contrasts the two state management policies implemented by the Copier (left) and Trailer (right) in MiniCP for the example shown in Listing 20. It is worth noting that the Trailer avoids creating unnecessary copies for untouched state objects.

Fig. 3

Illustration of the differences between Copier and Trailer related to example given in Listing 20

5.3 Revisiting the domain implementation

The domain of a variable is part of the state and must be saved and restored. So it is necessary to upgrade the implementation presented previously. The sparse set representation is convenient for this purpose. Assume that method saveState is called when the domain has size 8. In all subsequent forward computations, the array will contain a permutation of these 8 values in the first 8 slots. So, when restoring the state, it suffices to restore the size of the domain. Consider Fig. 3 again and assume that the state was saved before the removal of values 4 and 6. Then a restoreState operation restores the size to 9 (as it was at the time of the saveState) and the two removed values are reinserted in the set as expected. The permutation of values is not the same as when saveState was called but the domain captures the same set of values $\{0,\ldots ,8\}$. This is depicted in Fig. 4. For this reason, MiniCP simply provides a StateSparsetSet class which is the same as SparsetSet except that instance variable size is a state variable.

Fig. 4

Sparset set

Finally, observe that the sets of constraints stored in variables are also part of the state: Constraints can be added (and backtracked over). These sets can be implemented with a StateStack data structure whose implementation can simply use a StateInt to represent the size of the stack. On backtracking, the correct size, and hence the correct set of constraints, are restored. The brief implementation is shown in Listing 25.

5.4 Supporting optimization

The resolution of a Constraint Optimization Problem (COP) reduces to solving a sequence of constraint satisfaction problems. Without loss of generality, assume that the COP is a minimization. The basic idea behind a branch and bound is the following. Given a COP $\langle X,{\mathcal {D}},C,f\rangle$, first solve the CSP $\langle X,{\mathcal {D}},C\rangle$. As soon as a solution $\sigma$ is found, evaluate $f(\sigma )$ to obtain a first primal bound $f_1$ on the objective function and solve the second CSP $\langle X,{\mathcal {D}},C \cup \{ f < f_1 \}\rangle$. Repeat this process until the $k^{th}$ CSP $\langle X,{\mathcal {D}},C \cup \{ f < f_k \}\rangle$ becomes infeasible. This failure proves the optimality of the last feasible solution.

The implementation of MiniCP follows this scheme but with an important difference: It does not restart the search from scratch. Instead, it continuously tightens the objective $f < b$, where b represents the value of the best-found solution at some computation stage. The implementation is given in Listings 26 and 27 which show how to minimize the value of a variable. Listing 26 presents a class Minimize that implements interface Objective and supports only one method tighten which is called when the solver finds a solution (see line 16 in Listing 27). Its implementation simply tightens the best primal bound (i.e., the value of the best solution found so far) before failing to search for better solutions (lines 8–11). The implementation uses observers, i.e., closures attached to the search and executed when a solution is found.

It remains to ensure that the variable being minimized has the proper bound at all times. The bound update cannot be performed only when a new solution is found, since the update would be undone on backtracking. MiniCP applies the bound update systematically before each fixpoint (and hence after each branching), using an observer again (line 6 in Listing 26 adds the bound update to the fixpoint observer).

The extended DFSearch class in Listing 27 adds an optimize method to complement its solve method. The onSolution method registers listener closures in a solObserver list. The notifySolution method simply calls all the closures registered in the solution listener. Finally, the optimize method is modeled after solve –repeated above for clarity– and simply registers a solution listener that tightens the primal bound of the objective when a solution is produced. A similar implementation in the MiniCP class effectively implements the onFixPoint observer which is triggered as the first step of the fixpoint method of the solver.

6 Advanced filtering techniques

This section introduces some more advanced features of MiniCP for constraint propagation. In particular, this section presents variable views, anonymous constraints, reified constraints, and global constraints.

6.1 Variable views

The N-Queens program of Listing 1 states constraints of the form

$$\begin{aligned} q_i+i \ne q_j+j \wedge q_i-i \ne q_j-j \end{aligned}$$

by using a ternary constraint of signature

which holds if $x \ne y + c$. The approach of creating many variants of a constraint is motivated by efficiency considerations. Indeed, it is possible to rewrite each of the above constraints in terms of binary disequations, e.g.,

$$\begin{aligned} qp_i = q_i + i \wedge qp_j = q_j + j \wedge qp_i \ne qp_j, \end{aligned}$$

by introducing many intermediate variables and constraints. This removes the need for constraint variants but may slow down the overall efficiency of the fixpoint algorithm significantly. Fortunately, there is a third alternative that strikes a good compromise between efficiency and simplicity: variable views [24].³ A variable view is an IntVar variable that represents an affine transformation over a given variable. Views in MiniCP are built through the following classes

• IntVarViewMul for $c*X$,

• IntVarViewOffset for $X+o$ and

• IntVarViewOpposite for $-X$.

which can be composed to obtain affine transformations. The queens model using views is shown in Listing 28. Methods plus and minus creates views of type IntVarViewOffset, which are then used in binary disequations.

The implementation of the IntVarViewOffset class is illustrated in Listing 29. Queries on the views are delegated to the view variable after possibly adding or subtracting the offset. Value removal also delegates to the view variable after having subtracted the offset. Finally, constraints on the views are attached to the view variable.

6.2 Anonymous constraints

Sometimes the propagate method of a constraint is so small that it is inconvenient to build an entire class. MiniCP provides anonymous constraints to address these cases. Variables provide methods such as whenBind and whenDomainChange that receive as input a closure, create constraint whose propagate method calls the closure, and link the resulting constraints to the proper list in the variables.

Listing 30 illustrates anonymous constraints for the implementation of the NotEqual constraint. The constraint has no propagate method. All its tasks are carried out in method post. In particular, lines 15–16 specify what happens when variables x or y are bound. Anonymous constraints are particularly appealing in the sense that they can capture part of the lexical scope, providing compact implementations of many small constraints. A limitation of anonymous constraints is simultaneous deactivations. Therefore, an implementation with a propagate method deactivating the constraint when x or y is bound as in Listing 13 is more efficient in this case.

6.3 Reified constraints

The ability to reason about constraints in constraint-programming systems was introduced in cc(FD) [5, 25]. It is available in most modern systems through reified constraints (also called indicator constraints in mathematical programming). A reified constraint links a Boolean variable with the truth value of a constraint (0 is false and 1 is true). For instance, the reified constraint isEqual(x,v,b) holds if $b \equiv (x = v)$. Its implementation captures the following inference rules:

• when ${\mathcal {D}}(b)={1}$ then add constraint $x=v$;

• when ${\mathcal {D}}(b)={0}$ then add constraint $x \ne v$;

• when ${\mathcal {D}}(x)={v}$ then add constraint $b=1$;

• when $v \notin {\mathcal {D}}(x)$ then add constraint $b=0$.

The implementation is given in Listing 31. Notice the dynamic deactivation of the constraint whenever b or x is bound or whenever $v \notin {\mathcal {D}}(x)$.

6.4 Global constraints

Global constraints are a key aspect of constraint programming: They capture combinatorial substructures that are present in many application and which enjoy fast filtering algorithms. This section presents three simple examples of global constraints which are used in the QAP model given in Listing 3: The sum(weightedDist), the element(d,x[i],x[j]) and the allDifferent(x). Readers interested in global constraints should consult the global constraint catalog [26] or the surveys [27, 28].

The Sum Constraint The sum constraint enforces the relation $0 = \sum _{i=0}^{n-1} x_i$. Enforcing domain consistency for sum is NP-hard and this section presents an algorithm enforcing bound consistency. The bound-consistent inference rules for sum are:

• $\max ({\mathcal {D}}(x_i)) \leftarrow \sum _{j\ne i} -\min ({\mathcal {D}}(x_j))$

• $\min ({\mathcal {D}}(x_i)) \leftarrow \sum _{j\ne i} -\max ({\mathcal {D}}(x_j))$

Computing those rules for every variable takes $\mathcal{O}(n)$ per variable and hence $\mathcal{O}(n^2)$ overall. The complexity can be reduced to simply $\mathcal{O}(n)$ by precomputing $\mathrm {sumMax}=\sum _{j} \max ({\mathcal {D}}(x_j))$ and $\mathrm {sumMin}=\sum _{j} \min ({\mathcal {D}}(x_j))$. Those precomputed values allow for a $\mathcal{O}(1)$ inference rule for each variable:

• 1. $\max ({\mathcal {D}}(x_i)) \leftarrow \min ({\mathcal {D}}(x_i))-\mathrm {sumMin}$

• 2. $\min ({\mathcal {D}}(x_i)) \leftarrow \max ({\mathcal {D}}(x_i))-\mathrm {sumMax}$

In practice, further efficiency can be obtained by exploiting the incremental nature of the filtering process. Indeed, the number of bound variables when going down a branch of the depth-first search can never decrease. Hence, it is possible to pre-compute incrementally the sum of these bound variables and to iterate only on free variables. The implementation uses an integer array free and a counter nFrees to represent the indices of the variables and the number of free variables with the following invariants: The first nFrees indices in the array free represent free variables while the remaining variables are bound. The implementation also maintains sumFixed, the partial sum of bound variables

$$\begin{aligned} \mathrm {sumFixed} = \sum _{ i \ge \mathrm {nFrees}} x_{\mathrm {free}[i]} \end{aligned}$$

The values sumMax and sumMin can then be computed in $\mathcal{O}(\mathrm {nf})$ as follows:

$$\begin{aligned} \mathrm {sumMax} = \mathrm {sumFixed} + \sum _{j < \mathrm {nFrees}} \max ({\mathcal {D}}(x_{free[j]}) \end{aligned}$$

and

$$\begin{aligned} \mathrm {sumMin}= \mathrm {sumFixed} + \sum _{j < \mathrm {nFrees}} \min ({\mathcal {D}}(x_{free[j]}) \end{aligned}$$

Only the free variables are considered for filtering, i.e., $\forall i < \mathrm {nFrees}:$

• 1. $\max ({\mathcal {D}}(x_{free[j]})) \leftarrow \min ({\mathcal {D}}(x_{free[j]}))-\mathrm {sumMin}$

• 2. $\min ({\mathcal {D}}(x_{free[j]})) \leftarrow \max ({\mathcal {D}}(x_{free[j]}))-\mathrm {sumMax}$

The complete code is in Listing 32. The time complexity for one call to propagate is $\Theta (\mathrm {nFrees})$. The invariant on array free is maintained by iterating over the free variables from index nFrees$-1$ until 0 and in swapping, in $\mathcal{O}(1)$ time, any index whose variable is bound with the last free variable at index nFrees. The value assigned to the bound variable is also added to sumFixed. The set of bound variables only increases monotonically in a branch: Hence storing nFrees as a StateInt ensures that the invariant is still valid when backtracking. Obviously, this is similar to the state representation of sparse sets.

The Element Constraint The element constraint offers the ability of indexing arrays with decision variables [3, 29]. This functionality often avoids the introduction of many binary variables, as well as arrays of binary variables with many dimensions. This section considers an element constraint of the form $z = d_{x,y}$, where d is a two-dimensional array of constants of size $n \times m$ and x, y,  and z are variables. Moreover, the proposed implementation achieves domain consistency for variables x and y and bound consistency for variable z. This corresponds to a frequent case in practice; The implementation can easily be generalized to enforce domain consistency on all variables.

The implementation builds a sorted set of tuples $\langle i_1,j_1,v_1 \rangle , \ldots ,\langle i_p,j_p,v_p \rangle$ where $v_1 \le \cdots \le v_p$, $p = n m$, $0 \le i_k < n$, $0 \le j_k < m$, and $v_k = d_{i_k,j_j}$. This sorted set can be computed once in method post and makes it simple to filter variable z. The implementation scans the sorted set from below until it finds a tuple $\langle i_m,j_m,v_m \rangle$ such that $i_m \in {\mathcal {D}}(x)$, $j_m \in {\mathcal {D}}(y)$, and $v \ge \min ({\mathcal {D}}(z))$, producing v as the new lower bound. The new upper bound can be obtained similarly by iterating from above.

The filtering of variables x and y is slightly more involved. Consider variable x (variable y is similar). A value i for x may appear in many tuples and it is only when all these tuples cannot be solutions that value i can be removed from ${\mathcal {D}}(x)$. To implement the filtering efficiently, the implementation uses a counter $c_{x,i}$ (a StateInt variable) that represents the number of times value i appears in a possible solution, i.e., a tuple $\langle i, j, v \rangle$ such that $i_m \in {\mathcal {D}}(x)$, $j_m \in {\mathcal {D}}(y)$, and $\min ({\mathcal {D}}(z)) \le v \le \max ({\mathcal {D}}(z))$. These counters are assigned to m initially, since no processing takes place in method post.

Method propagate filters all variables in two scans: one from below and one from above. When iterating from below (the other case is similar), the implementation considers each tuple. If the tuple $\langle i, j, v \rangle$ is a possible solution, the sweep stops and the minimum of variable z is updated to v. Otherwise, the counters $c_{x,i}$ and $c_{y,j}$ are decremented. If a counter reaches zero, then the value is removed from the domain of the corresponding variable. To avoid considering a tuple more than once, the implementation also maintains two indices low and up (represented by StateInt) to remember where to start the below and above scan of the sorted set of tuples. The full implementation is given in Listing 33.

The AllDifferent Constraint An $\texttt {allDifferent}(x_0,\ldots ,x_{n-1})$ ensures that every variable in $\{x_0,\ldots ,x_{n-1}\}$ takes a different value. Decomposition into elementary binary constraints such as $\forall i \ne j: x_i \ne x_j$ does not enforce domain consistency globally. For instance, the decomposition does not detect inconsistency for the domains ${\mathcal {D}}(x_0)={\mathcal {D}}(x_1)={\mathcal {D}}(x_2)=\{1,2\}$, which is directly implied by the pigeonhole principle. It is interesting to outline how to implement consistency on the global constraint to highlight how constraint programming may leverage combinatorial algorithms.

Detecting feasibility can be achieved by solving a maximum matching problem in the bipartite value graph $G(V_1,V_2,E)$ with $V_1= \{x_0,\ldots ,x_{n-1}\}$ and $V_2=\bigcup _{i \in 0..n-1} = {\mathcal {D}}(x_i)$, $E=\{(i,v) \mid v \in {\mathcal {D}}(x_i)\}$. The constraint is satisfiable if and only if the maximum matching has cardinality n. The rest of the presentation assumes that $V_2=\{0,\ldots ,m-1\}$ without loss of generality.

Filtering the allDifferent constraint amounts to determining whether an edge in the bipartite graph belongs to some maximum matching. This can be achieved by solving a matching problem for every edge. Régin [30] however showed that this filtering can be performed in time linear in the size of the graph. The algorithms is composed of four steps illustrated in Fig. 5 and summarized as follows:

• 1. A maximum-size matching M is computed in the value graph.

• 2. The residual graph is constructed.

• 3. The strongly connected components (SCC) are computed in the residual graph.

• 4. Every edge belonging to some SCC belongs to a maximum matching and edges between SCCs do not. Hence these edges can be filtered.

A sketch of the implementation is given in Listing 34. The object in charge, MaximumMatching, computes the maximum matching in the value graph. This object wraps an augmenting path algorithm. Although the details of the implementation are not given here, this algorithm is incremental in the following sense: From one call to the next at line 29, it restarts its computation from the previous matching and needs only as many augmenting steps as the number of deleted edges. In addition, the matching remains valid upon backtracking. The feasibility test is computed at line 30, throwing an InconsistencyException in case $|M|<n$. Line 32 updates the residual graph. Line 33 computes the SCC. e.g, using Tarjan’s or Kosaraju’s algorithm. This computation is hidden in the method call

where g is the residual graph. It returns an array associating a SCC identifier with each node of the graph (i.e., each variable and value). Finally, line 37 removes any value v from the domain of a variable x if the corresponding edge is not in M and if the SCCs of x and v are different. A comprehensive discussion of this algorithm can be found in [31].

Fig. 5

Illustration of the allDifferent constraint. Step 1: nodes contain the variable indices and values. Step 2: nodes contain canonical id’s in the residual graph. Step 3: component ids are given in each node and colors represent those ids. Step 4: removed edges are represented with dashed lines

7 Advanced search techniques

This section presents some advanced search techniques. It shows how to implement search limits, combinators, and large neighborhood search in MiniCP.

7.1 Search limits

In various circumstances, it is desirable to terminate the search before having found all solutions or the optimal solution. MiniCP provides a simple abstraction to implement various search limits, e.g., on the number of solutions, the CPU time, or the number of failures. Method solve accepts a predicate (a Java closure) which is applied at every node of the search to decide whether to terminate the search early. For instance, the fragment

illustrates how to terminate the search once the first solution has been found. The closure receives an argument stat (of type SearchStatistics) that collects statistics about the search. In this example, the boolean predicate simply checks the number of solutions recorded in stat. The generalized implementation of depth-first search is shown in Listing 35. Line 8 contains the more general solve call. The DFS search in line 17 receives, as inputs, the statistics object and the stopping predicate, which are used before branching to determine whether to terminate the search.

7.2 Search combinators

Search combinators in MiniCP compose branching schemes to produce more sophisticated branching schemes. This section illustrates how to build search combinators in MiniCP through an example.⁴ Listing 36 shows how to implement search phases, where the search composes several branching schemes in sequence. Such a combinator is useful to implement search phases which are often used to prioritize the assignment of certain variables over others.

Recall that a branching scheme returns an array of branches, which is empty when the scheme completes. To compose a sequence of those, it suffices, at each node of search tree, to iterate over the schemes until one produces a non-empty array of branches. The Sequencer combinator receives, as input, an array of branching schemes. When called to produce a set of branches, it iterates over the branching schemes until one produces a non-empty array (lines 8–12). Note the compositional nature of the combinator: The combinator itself is a branching scheme and it applies to any branching scheme.

Combinators can be composed with generic selectors to specify complex branching schemes concisely. Consider the implementation of a search procedure that assigns two arrays of variables a and b in sequence, using the first-fail principle (i.e., the variable with the smallest domain is assigned first). The high-level specification is as follows:

The rest of the implementation is depicted in Listing 38, which provides an excerpt of the class BranchingScheme. Lines 5–14 define a selector that receives, as inputs, an array x, a predicate p, and a function f: It selects an element xi of x such that p(xi) holds and f(xi) is minimal. Lines 16–29 define a search procedure that uses the first-fail principle to assign all variables in array x. It uses selectMin to find the free variable with the smallest domain and then branches in the same way as in the prior examples. Note Lines 30–32 that define a factory method and to create a sequencer combinator.

7.3 Limited discrepancy search

This section presents a combinator for Limited Discrepancy Search (LDS) [35]. LDS assumes that a reasonably good heuristic is available and explores by trusting the heuristic less and less over time. It often helps DFS from being stuck in unproductive parts of the search space. LDS explores the search in waves, allowing the search to differ from the heuristic by up to 0, 1, 2, $\ldots$ decisions in each wave. For instance, Fig. 6 displays the leaves explored by LDS with a discrepancy limit of 2.

Fig. 6

Illustration of the nodes explored with a discrepancy limit of 2. The discrepancy is given in each node. Dashed nodes are pruned

The Implementation of LDS in MiniCP is given in Listings 39 and 40. Listing 39 describes a combinator for implementing a wave, while Listing 40 presents the traditional iterative implementation of LDS. Any branching scheme can be wrapped into the LDS combinator to create a new branching scheme. The key is to create new closures from the embedded branching schemes. Each such closure updates the current discrepancy curD (line 21) before calling the actual branch. The current discrepancy is then used in line 15 to fail if the discrepancy limit maxD is exceeded. Note that the nodes explored in a given iteration of Listing 40 may overlap with the ones explored at the previous iteration. But this overlap is in general quite limited since most of them are pruned with the help of the primal bounds produced by the waves.

7.4 Large neighborhood search

Large Neighborhood Search (LNS) [36] is an effective search strategy to leverage the strengths of CP on large-scale applications. Its key idea is to improve an initial solution by fixing some of its decisions and searching for an improving solution when exploring the remaining search space. The sub-space exploration (often called a reconstruction phase) is often subject to a CPU time or failure limits to avoid being stuck. This process is repeated using randomization to select the subspaces. For instance, the subspace may be defined by fixing the assignments of a subset of the decision variables, the remaining variables being “relaxed”, i.e., they can be assigned to any value in their domain. Table 2 highlights this process on the first four iterations of the quadratic assignment problem. It depicts the vector of decision variables and objective value. At each iteration, about $50\%$ of the variables are randomly selected to be assigned to their value in the best-found solution, the other being “relaxed”. CP then tries to improve the current best solution.

Table 2 The first four iterations of LNS on the quadratic assignment problem

An implementation of LNS in MiniCP is given in Listing 41. Line 1 defines an array xBest to store the best-found solution. Lines 3–8 updates this array every time a new solution is found. Lines 10–23 performs nRestarts CP searches. Each such exploration starts by fixing about 50% of the variables to their values in the best-found solution (lines 15–20), before proceeding to the depth-first search itself. Method optimizeSubjectTo calls withNewState to preserve the initial state in which none of the variables are fixed. Therefore, at each iteration, this initial state is restored before starting fixing the selected variables. For completeness’ sake, method optimizeSubjectTo is shown in Listing 42.

8 Teaching material and student projects

MiniCP comes with a series of more than 20 implementation projects available on https://bitbucket.org/minicp/minicp. All the projects can be tested with junit-tests provided to students. These projects will teach students the material presented in this paper, as well as more advanced topics. They include

• Trailing and CP solver internal mechanisms by adding new useful functionalities to MiniCP (views, domain iterators, etc);

• Basic binary, logical, and reified constraints;

• Global constraints: table, element, allDifferent constraints;

• Problem specific and black-box heuristics, including LNS;

• Modeling good practices (redundant constraints, symmetry breaking, ...);

• Scheduling constraints;

• CP for frequent pattern mining, an emerging topic.

Slides that provide the required background to successfully implement the projects are also available. At the end of each slide deck, suitable implementation projects are identified. This material has been already used and tested at the ACP-2017 summer school and in the ING2365 course on CP at UCLouvain. The proposed projects are calibrated to take about 4 hours of implementation work for 12 weeks. In the future, some quizzes and homeworks will also be developed. A mini-solver competition was recently organized [37] for solving problems described by XCSP3 standardized modeling format. MiniCP comes with a parser and interface for the XCSP3 format to simplify participation. Students found the participation in a competition very motivating.

9 Conclusion

This paper introduced MiniCP, a light-weight, open-source constraint programming solver for educational purposes. Its goal is to stimulate the teaching and research in constraint programming by democratizing access to its core implementation concepts. MiniCP has a minimalist architecture with a close matching between theoretical and implementation concepts and a focus on compositionality and extensibility.

MiniCP is a living project already used in practice to teach constraint programming at some universities and in summer schools. It will continue to evolve and offer new teaching material. The version described in this paper is 1.0.1. The project welcomes contributions and extensions under the form of pull requests on the source code, exercises, or as new reference to external pages. Feedback from Early adopters indicates that MiniCP is also useful for research purposes as it permits to experiment with new ideas easily in a clean and understandable, yet reasonably efficient, architecture.

Appendices

Java closures

Java 1.8 supports the concept of closures (aka first-order functions) which is at the core of functional programming. The MiniCP solver makes extensive use of closures for more readibility and conciseness. Consider the identity function $\lambda x.x$ expressed in lambda-calculus. It can be written in Java 1.8 as

The code indicates that Java provides a generic type ${\texttt {Function<A,B>}}$ to represent a function of type $A \rightarrow B$. and r is used to refer to the identity function. The next two lines show how to apply closure r for various values. Since this example is somewhat verbose, Java 1.8 offers syntactic sugar to simplify the notation, dropping the argument type, the block syntax, and the return keyword to obtain

This brings the definition of r close to a lambda calculus definition. Java 1.8 also makes it possible to define arbitrary closure types through the concept of functional interface. For instance, the snippet

defines the type of a closure that takes no input and return no outputs. It just executes a block of code. MiniCP also makes extensive use of functional interfaces defined in the JDK 1.8. For instance, a branching (closure returning an array of Procedure) is none other than ${\texttt {Supplier<Procedure[]>}}$. Boolean predicates over some type T (i.e., first-order functions of type $T \rightarrow \mathbb {B}$ use ${\texttt {Predicate<T>}}$ while first-order functions of type $T \rightarrow N$ use ${\texttt {Function<T,N>}}$.

Performance evaluation

The objective of those experiments is to measure the raw performances of the basic funtionalities offered by a solver: backtracking and propagation mechanisms, domains, search, etc. Our goal is to measure if, despite its simplicity, MiniCP achieve reasonable performance when compared to carefully engineered and optimized solvers, including Choco [14] (version 4.0.2) implemented in Java and OscaR [9] (version 4.0.0) implemented in Scala. Both [14] and [9] have more than 50K lines of code. The MiniCP version used in the test is 1.0.1. Table 3 was obtained on a MacBook Pro with a 2.6Ghz 6-Core i7 running macOS Catalina 10.15.1. The Java version used is

Runtime were obtained by using the time command of the operating system as in, for instance:

and reporting the wall clock time.

Table 3 Performance comparison with Choco [14] and OscaR [9]

In state-of-the-art solvers, great care is dedicated to the efficient implementation of global constraints. Since comparing implementations of global constraints is not the purpose of this evaluation, the models used in the experiments and available here https://zenodo.org/record/3557449 are quite simple and composed of sum, elements, reification and binary constraints. The experimental evaluation ensures that the same search trees is explored by all the solvers. The evaluation also forces a sparse-representation of the domains as this is the only available option in MiniCP in the base implementation.

Table 3 presents the results and running times are given in seconds. The performance of MiniCP is reasonably good despite its simplicity, flexibility and the fact that we explicitly refrain from optimizing the implementation. For instance, the code uses Java collections which induce a significant overhead due to object and iterator creations; An optimized solver such as OscaR or Choco often uses its own array-based collections. Boolean variables in MiniCP are simply 0/1 integer variables, while OscaR uses a dedicated implementation. OscaR statically pre-allocates frequently used objects to avoid the dynamic creation of StateEntries. Aside from this lack of optimization in memory management, the performance difference can be explained by the fact that OscaR and Choco have a priority system to schedule light constraints before more complex ones. While the default implementation of MiniCP has no constraint priorities, adding the necessary support is straightforward and un-intrusive. First, one must add a constant attribute (and an accessor) to each constraint instance to hold onto a priority level (a value from a discrete subset of integers, e.g., 0 through k where k is the highest priority). Second, the state of MiniCP solver class (Listing 15) must be upgraded to hold onto a vector of ${\texttt {Queue<Constraint>}}$, one for each discrete priority. Third, when a constraint c is scheduled, it gets added to the propagation queue matching c’s priority (changes to method schedule of MiniCP. Finally, the fixpoint algorithm (method fixPoint of MiniCP) must, at each iteration, determine the highest non-empty priority queue and pull the next constraint from there. Once all queues become empty, the fixpoint is reached and one can break out of the loop.