Arc Consistency via Linear Programming

Abstract

A typical technique in integer programming for filtering variables is known as variable fixing. The optimal dual solution of the linear relaxation can be used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known, but this filtering is incomplete. A complete technique is proposed in this paper for satisfaction problems with an ideal integer programming formulation. We show, in this case, that the 0/1 variables taking the same value in all solutions can be identified by solving a single linear program with twice the number of the original variables. In other words, a complete variable fixing of the 0/1 variables can be performed for a small overhead. As a result, this technique can be used to design generic arc consistency algorithms. We believe it is particularly useful to quickly prototype arc consistency algorithms for numerous polynomial constraints and demonstrate it for the family of Sequence global constraints.

1 Introduction

Mixed integer programming (MIP) and Constraint Programming (CP) have benefited from each other increasingly in recent years due to the complementary strengths of the two frameworks. Many approaches have been proposed to combine their modeling and solving capabilities [1, 2, 6, 18, 21]. On one side, CP tailored algorithms for specific constraints take advantage of local combinatorial structures to reduce the search space efficiently. On the other, MIP techniques usually encompass the whole problem and typically compute lower/upper bounds of the objective function that propagation through the domains fails to derive. A typical integration of the two approaches is to use the linear relaxation of the entire problem in addition to the local consistencies enforced by the CP solver. The relaxation is used to perform filtering, in particular by providing a global bound of the objective but also by filtering the domains using a technique referred to as reduced-cost-based filtering [11, 14]. Constraints can in turn provide specialized linear formulations and cutting planes.

As opposed to previous work, we investigate in this paper how linear programming (LP) can be used to filter individual constraints and in particular to provide arc consistency algorithms. Let us suppose that an ideal linear formulation $\mathcal{F}$ over n variables is available for a global constraint. A formulation is referred to as ideal when it has the integrality property i.e. when the extreme points of the corresponding polytope are integer points. It is easy to come by such formulations for many global constraints [18] that include 0/1 variables typically encoding whether an original variable of the constraint is assigned to a given value of its domain. Since $\mathcal{F}$ is supposed ideal, a simple way to achieve arc consistency is to fix, in turn, each variable to each value and check the consistency by calling a linear solver. This is very similar to the failed literal test mentioned in [3] for achieving arc consistency with unit propagation over a SAT encoding of the constraint.

We show, however, that arc consistency can be achieved in this case by solving a single linear program with n additional variables and 2n additional constraints. The idea is to look for an interior point, of the convex hull of $\mathcal{F}$ maximizing the number of variables with a slack to their respective lower and upper bounds. Although this goes against the rationale explained above for integrating the two frameworks, we believe the advantages are twofold. First of all, since each solver only provides a handful of the existing constraints, it is particularly useful to quickly design arc consistency algorithms for many polynomial constraints. Secondly, it can provide a generic but competitive algorithm for constraints with a quadratic running time such as the Gen-Sequence [13].

The linear relaxation has been used in the past for filtering and we now review several closely related works [1, 2, 18, 21] that propose frameworks for combining the linear relaxation, specialized cutting planes generation and filtering. An illustrative example is the work of [18] where each constraint is able to provide its linear relaxation so that a global relaxation of the entire problem is automatically derived from a CP model. Additionally, a constraint is able to add dedicated cutting planes during search, taking advantage of the corresponding combinatorial structure to build a stronger relaxation. The linear relaxations of common global constraints such as Element, AllDifferent, Circuit and Cumulative can be found in [12, 18] and relaxations of global constraints involving costs such as MinimumWeightAlldifferent or WeightedCircuit are described in [10]. The linear relaxation is directly used for filtering by [1, 2, 10, 17, 18]. It can detect infeasibility, provide a bound for a cost variable and perform filtering using a technique referred to as reduced-cost based filtering [10, 11]. The latter is a specific case of cost-based filtering [9] that aims at filtering out values leading to non-improving solutions.

Section 2 summarizes the key notations. Section 3 reviews and explains reduced-cost based filtering in more details. The main result of this paper is presented Sect. 4 and its application to AllDifferent, GlobalCardinality and Gen-Sequence constraints is described in Sect. 5. Finally experimental results are reported on three benchmarks in Sect. 6.

2 Notations

A constraint satisfaction problem is made of a set of variables, each with a given domain, i.e. a finite set of possible values, and a set of constraints specifying the allowed combinations of values for subset of variables. In the following, the variables, e.g. $X_i$, are denoted with upper case letters for the constraint programming models as opposed to the variables of linear programming models that are in lower case. $D(X_i) \subseteq \mathbb {Z}$ denotes the domain of $X_i$. A constraint C over a set of variables $\langle X_1, \ldots , X_n \rangle$ is defined by the allowed combinations of values (tuples) of its variables. Such tuples of values are also referred to as solutions of the constraint C. Given a constraint C with a scope $\langle X_1, \ldots , X_n \rangle$, a support for C is a tuple of values $\langle v_1,\ldots , v_n \rangle$ that is a solution of C and such that $v_i \in D(X_i)$ for all variable $X_i$ in the scope of C. Consider a variable $X_i$ in the scope of C, the domain $D(X_i)$ is said arc consistent for C if and only if all the values $v_j \in D(X_i)$ belong to a support for C. A constraint C is said arc consistent if and only if all its variables are arc consistent.

3 Traditional Filtering Using LP: Reduced-Cost Filtering

Let us first review how linear programming is traditionally used to perform filtering. Suppose we are dealing with a minimization problem. Cost-based filtering relies on a known upper bound $\overline{z}$ of the objective function which is usually the cost of the best feasible solution found so far. Since there is no need to consider solutions with a greater cost that $\overline{z}$, values of the domains that would necessarily lead to such non-improving solutions should be filtered. Linear reduced-costs provide valuable information to perform such reasonings. They are available from an optimal dual solution of the linear relaxation and give a minimum increase of the objective function. This increase can be used to detect if a bound of a variable leads to a non-improving solution. When applied to 0/1 variables, i.e. variables with the domain $\{0,1\}$, any update of a bound leads to fixing a variable to 0 or 1. It has thus been known for a long time as variable fixing.

To our knowledge, the best account of this technique in the context of constraint programming is given in [11]. It is usually presented in textbooks on integer programming such as [14, 26] for 0/1 variables. We give a summary of this technique in the more general case of integer variables. Consider a linear programming formulation (P) where the feasible region is defined by a polytope $\mathcal{Q}=\{x\in \mathbb {R}^{T}\;|\;Ax\ge b, l\le x\le u\}$. Note that each variable $x_t$ for all $t\in \{1,\dots ,T\}$, has a given lower and upper bound i.e. $x_t \in [l_t, u_t]$.

$$ (P) \qquad z^* = \min \{cx : x \in \mathcal{Q}\} $$

Program (P) is typically the linear relaxation of an integer programming formulation identified for the whole problem or for a single constraint. Let $\alpha$ be the m dual variables of the constraints $Ax\ge b$. Moreover, let $x^*$ be an optimal solution of (P) and $\alpha ^*$ a set of optimal values of the $\alpha$ variables. The reduced cost $r_t$ of a variable $x_t$, with respect to $\alpha ^*$, is defined as $r_t = c_t - \alpha ^*A_t$ where $A_t$ is the t-th column of A. Note that the definition of $r_t$ ignores the dual variables related to the lower and upper bounds since $x_t \le u_t$ and $x_t \ge l_t$ are usually not added as constraints to the formulation of (P) but handled directly by the simplex algorithm (see [8] for more details). The reduced cost $r_t$ is typically the quantity returned by linear programming solvers when the bounds are not explicitly stated as constraints in the model but directly as bounds of the variable’s domains.

Reduced-cost-based filtering removes values necessarily leading to non-improving solutions i.e. solutions of cost greater than the known upper bound $\overline{z}$. The following rules can be used for filtering a variable $x_t$ of (P) from an optimal dual solution.

Proposition 1

(Reduced cost filtering).

(1)

(2)

Note that if $x_t$ is originally an integer variable, the reasoning can be tightened as $x_t \le l_t+ \lfloor \frac{(\overline{z} - z^{*})}{r_t}\rfloor$ and $x_t \ge u_t- \lfloor \frac{(\overline{z} - z^{*})}{-r_t}\rfloor$.

The two rules are a direct consequence of traditional sensitivity analysis and the reader can refer to [11, 26] for more details.

The filtering obtained from a particular optimal dual solution is usually incomplete since $r_t$ depends on the specific $\alpha ^*$ found. In other words, considering several optimal dual solutions may provide more filtering. Let us go through a very simple example to illustrate this point. We consider a difference constraint $X_1 \ne X_2$ with $D(X_1) = \{1,2\}$ and $D(X_2) = \{1\}$. Value 1 of $D(X_1)$ is thus expected to be filtered. A simple integer formulation of the feasible solutions can be written with 0/1 variables $x_1,x_2,x_3$ respectively encoding whether $X_1 = 1$, $X_1 = 2$ or $X_2 = 1$. The linear relaxation and its dual problem write as follows:

$x^*=(0,1,1)$ is an optimal solution of (P). It is easy to see that $\alpha ^* = (0,0,0,0)$ or $\alpha ^* = (0,1,-1,0)$ are two vectors of optimal values for $\alpha$ (with $\beta ^* =(0,0,0)$). The reduced cost of $x_1$ is $r_1 = 0-\alpha ^*_1-\alpha ^*_3 - \alpha ^*_4$. In the first case, $r_1 = 0$ and none of the rules given in Proposition 1 is triggered. In the second case, $r_1 = 1$ and the first rule applies with $\overline{z}=0$ enforcing $x_1 \le 0$ as expected. In both cases $r_2 = r_3 = 0$, therefore $x_2$ and $x_3$ are not filtered.

Note that this drawback occurs even if the polytope $\mathcal{Q}$ has integer extreme points which is the case in the example. Moreover, in any case, minimizing 0 in (P) implies that $\alpha ^*=0$ is an optimal vector for $\alpha$ and the linear solver can always return it. To reduce this phenomenon, it is possible to use another objective function cx as long as all feasible solutions have the same cost (see Sect. 6 for an example).

An alternative approach to reduced costs is proposed in the next section to perform a complete variable fixing.

4 A New Generic Filtering Algorithm Based on LP

Let us briefly explain the general idea and its application to filtering global constraints before stating the result in detail.

Consider a polytope $\mathcal{Q}=\{x\in \mathbb {R}^{T}\;|\;Ax \ge b, l\le x\le u\}$ with integer extreme points and $l,u\in \mathbb {Z}^{T}$. We show in this section that a variable that is fixed to one of its bound (either $l_t$ or $u_t$) in all extreme point of $\mathcal{Q}$ can be detected by solving a linear program with T additional variables and 2T additional constraints. The idea is to look for an interior point of $\mathcal{Q}$ maximizing the number of variables with a slack to their respective lower and upper bounds. When no slack is possible, the variable is proved to be fixed to the same value in all extreme points.

For numerous polynomial global constraints, it is possible to give an ideal integer programming formulation $\mathcal{F}$ of the solutions where 0/1 variables $x_{ij}$ typically encode whether an integer variable $X_i$ of the constraint’s scope is assigned to value a $v_j$ of its domain. The linear relaxation of $\mathcal{F}$ defines a polytope $\mathcal{Q}$ that represents the convex hull of the supports of the constraint. Each integer point in $\mathcal{Q}$ can be seen as a support of the constraint. The proposed technique identifies all 0/1 variables that are set to 0 in all extreme points. Since all interior points of $\mathcal{Q}$ are a convex combination of the extreme points, the same variables are thus also set to 0 for all interior points of $\mathcal{Q}$, i.e. the corresponding values do not belong to any support. Since complete variable fixing can be performed (all inconsistent values are removed), the proposed technique gives the arc consistent domains for the constraint.

The main result is stated as Theorem 1. The polytope $\mathcal{Q}=\{x\in \mathbb {R}^{T}\;|\;Ax \ge b, l\le x\le u\}$ is assumed to have integer extreme points and $l,u\in \mathbb {Z}^{T}$. Let us also denote by $\mathcal{S}$ the set of extreme points of $\mathcal{Q}$.

Theorem 1

Let us define $\displaystyle \varepsilon =\frac{1}{(T+1)}$, and $(P')$ the following linear program:

For all $t\in \{1,\ldots ,T\}$, all $\delta \in \{l_{t},u_{t}\}$, and all optimal solution $(x^*,e^*)$ of $(P')$ we have:

Note that a feasible solution of $(P')$ with $e_t = 0$ indicates that variable $x_t$ has a slack of at least $\varepsilon$ to its lower and upper bound. Keep also in mind that the objective of $(P')$ is to minimize the sum of the $e_t$ which tend to create slack. We will show that any optimal solution of $(P')$ actually maximizes the number of variables that can be unstuck from their bounds revealing all the $x_t$ that are always instantiated to either $l_t$ or $u_t$. We first make a simple observation:

Remark 1

If $(x^*,e^*)$ is an optimal solution of $(P')$, then $e^*=e(x^*)$ with $e:\mathbb {R}^T\rightarrow \mathbb {R}^T$ such that $e(x)=(e_1(x),\ldots ,e_t(x),\ldots ,e_T(x))$ and

$$e_t(x)=\max \{0,\varepsilon + l_t-x_t,\varepsilon -u_t+x_t\} \quad \forall t\in \{1,\ldots ,T\}$$

Proof: Each variable $e_t$ only occurs in three constraints of $(P')$: $e_t \ge 0$, $e_t \ge \varepsilon + l_t - x_t$ and $e_t \ge \varepsilon - u_t + x_t$. Given a value of $x^*$, the minimum possible feasible value for $e_t$ is thus $\max \{0,\varepsilon + l_t-x_t,\varepsilon -u_t+x_t\}$. $\square$

The optimal objective value of $(P')$ is at least $\varepsilon$ times the number of variables that are necessarily fixed to either $l_t$ or $u_t$. The proof given below builds a feasible solution of $(P')$ reaching this bound by setting $e_t(x) = 0$ for all other variables. Thus, any optimal solution highlights the fixed variables.

Proof of Theorem 1 :

We denote by $\mathcal{T}^l=\{t\in \{1,\ldots ,T\}\;|\;\hat{x}_t=l_t, \;\forall \hat{x}\in \mathcal{S}\}$ and $\mathcal{T}^u=\{t\in \{1,\ldots ,T\}\;|\;\hat{x}_t=u_t, \;\forall \hat{x}\in \mathcal{S}\}$ the sets of indices referring to variables fixed respectively to their lower or upper bounds, in all extreme points of $\mathcal{Q}$. As mentioned above, a valid lower bound $(P')$ is $\varepsilon (|\mathcal{T}^l|+|\mathcal{T}^u|)$.

Let $(\hat{x}^0,\hat{x}^1,\hat{x}^2,\ldots ,\hat{x}^T)$ be a series of extreme points of $\mathcal{S}$ defined as follows. $\hat{x}^0$ is chosen arbitrarily in $\mathcal{S}$. Each $\hat{x}^t$ such that $t\notin \mathcal{T}^l\,\cup \,\mathcal{T}^u$ is chosen in $\mathcal{S}$ so that $\hat{x}^t_t\ne \hat{x}^0_t$. Finally, all remaining $\hat{x}^t$ are chosen arbitrarily in $\mathcal{S}$.

Based on this series of points, we can define a feasible solution $(\bar{x},e(\bar{x}))$ of $(P')$ by considering $\bar{x}$ as the following convex combination $\displaystyle \bar{x}=\frac{1}{T+1}\sum _{t=0}^T\hat{x}^t$.

Firstly, note that $\bar{x}_t\in \{l_t,u_t\}$ if and only if $t\in \mathcal{T}^l\,\cup \,\mathcal{T}^u$. Indeed, $l_t\le \hat{x}_t\le u_t$ for all $\hat{x}\in \mathcal{S}$, so we have $\bar{x}_t\in \{l_t,u_t\}$ if and only if $\hat{x}^{t'}_t=\bar{x}_t$ for all $t'\in \{0,\ldots ,T\}$. Therefore, by construction, $\bar{x}_t\in \{l_t,u_t\}$ if and only if $\hat{x}_t=\hat{x}^0_t$ for all $\hat{x}\in \mathcal{S}$, i.e. $t\in \mathcal{T}^l\,\cup \,\mathcal{T}^u$.

Secondly, all other $\bar{x}_t$ have a slack of at least $\varepsilon$. For all $t\notin \mathcal{T}^l\,\cup \,\mathcal{T}^u$, we have $\hat{x}^{t}_t\ne \hat{x}^{0}_t$, therefore $\max \{\hat{x}^{t}_t,\hat{x}^{0}_t\}\ge l_t+1$ and $\min \{\hat{x}^{t}_t,\hat{x}^{0}_t\}\le u_t-1$ since extreme points of $\mathcal{Q}$ are integers. As a result:

Hence for all $t\in \{1,\ldots ,T\}$, we have

$$ e_t(\bar{x})=\left\{ \begin{array}{rlll} \varepsilon &{} \text{ if } t\in \mathcal{T}^l\,\cup \,\mathcal{T}^u\\ 0&{} \text{ otherwise } \end{array} \right. $$

Thus $z(\bar{x},e(\bar{x})) = \varepsilon (|\mathcal{T}^l|+|\mathcal{T}^u|)$ which proves that the solution $(\bar{x},e(\bar{x}))$ is optimal. Any optimal solution $x^*$ must therefore have a cost of $\varepsilon (|\mathcal{T}^l|+|\mathcal{T}^u|)$. Since $e_t(x^*) \ge 0$ for all t and $e_t(x^*)=\varepsilon$ for all $t\in \mathcal{T}^l\,\cup \,\mathcal{T}^u$, $e_t(x^*)=0$ for all $t\notin \mathcal{T}^l\,\cup \,\mathcal{T}^u$.

Conclusion: for all optimal solutions $(x^*,e^*)$ of $(P')$, all $t\in \{1,\ldots ,T\}$ and all $\delta \in \{l_t,u_t\}$,

   $\square$

We now propose a simple application of this result to filtering global constraints. Consider a polynomial global constraint C over a scope $X = \langle X_1, \ldots , X_n\rangle$ of n integer variables with their respective domains $D(X_i) \in \mathbb {Z}$. The approach proposed to enforce arc consistency is summarized below:

LP-Based Filtering for Constraint C :

Inputs: A constraint C over the variables $\mathcal{X} = \langle X_1, \ldots , X_n \rangle$. An ideal integer formulation $\mathcal{F}$ of the solutions of C where a 0/1 variable $x_{ij}$ is present for all $X_i \in X, v_j \in D(X_i)$ to encode whether variable $X_i$ takes value $v_j$.

Output: arc consistent domains $D(X_1),\ldots ,D(X_n)$ for constraint C

• 1. Consider $\mathcal{Q}$ as the convex hull of $\mathcal{F}$ by simply relaxing the domain’s constraint $x_{ij} \in \{0,1\}$ into $x_{ij} \in [0,1]$ for all $x_{ij}$

• 2. Find an optimal solution $(x^{*},e^{*})$ of $(P')$ as defined in Theorem 1

• 3. For each $X_i \in \mathcal{X}$ and each $v_j \in D(X_i)$, if $x^*_{ij} = 0$, remove value $v_j$ from $D(X_i)$.

The procedure given above computes arc consistent domains as a direct consequence of Theorem 1: indeed $x^*_{ij} = 0$ means that $x_{ij} = 0$ for any solution of the LP, hence the corresponding value has to be removed. Furthermore, when $x^*_{ij} = 1$, $x^*_{ik} = 0$ for all $k \ne j$.

Corollary 1

The procedure LP-based filtering is correct and establishes arc consistency for constraint C.

Proof: Recall that the integer points of $\mathcal{Q}$ represent the supports of C. Since any interior point can be written as a convex combination of the extreme points, there exists at least one extreme point $\hat{x}\in \mathcal{S}$ such that $\hat{x}_{ij}=1$ for any consistent value $v_j$ of a $D(X_i)$. Similarly when all $\hat{x}_{ij} = 0$ for all $\hat{x}\in \mathcal{S}$, it is the case of all interior integer points. Keeping that in mind, we simply check that the procedure does not remove any consistent value (it is correct) and removes all inconsistent values (it is complete).

Correct: consider a consistent value $v_j$ in $D(X_i)$. Since it belongs to a support, there exists at least one $\hat{x}\in \mathcal{S}$ such that $\hat{x}_{ij} = 1$. Therefore, $x^*_{ij} \ne 0$ according to Theorem 1 and value $v_j$ is not removed by the proposed procedure.

Complete: Let us check that all remaining values belong to a support. Consider a value $v_j$ of a domain $D(X_i)$ after the procedure has been called. Since $v_j$ has not been filtered, $x^*_{ij} \ne 0$ implying by Theorem 1 that there exists at least one extreme point $\hat{x}\in \mathcal{S}$ such that $\hat{x}_{ij} = 1$. Therefore $v_j$ belongs to the corresponding support.$\square$

The complexity of LP-based filtering depends on the algorithm used to solve the LP. In practice, the simplex algorithm is known to have a number of iterations proportional to $m \log (n)$ [8] where n is the number of variables and m the number of constraints of the LP formulation.

5 Ideal Linear Formulations of Polynomial Global Constraints

We now provide an ideal integer programming formulation $\mathcal{F}$ for a number of polynomial global constraints. The fact that a variable $X_i$ takes one and one value only of its domain ($X_i \in D(X_i)$) is typically expressed in $\mathcal{F}$ following [18]:

$$\begin{aligned} \left\{ \begin{array}{rlll} \sum \limits _{v_j \in D(x_i)} x_{ij} &{}=&{} 1 \\ x_{ij} &{}\in &{} \{0,1\} &{} \qquad \forall v_j \in D(X_i) \end{array} \right. \end{aligned}$$

(3)

5.1 AllDifferent and GlobalCardinality

The $\textsc {AllDifferent}(X_1,\ldots , X_n)$ constraint [19] is satisfied when the variables $X_1, \ldots , X_n$ take different values. The formulation given below is the classical formulation for the matching problem and is known to have the integrality property:

$$\begin{aligned} \mathcal{F} = \left\{ \begin{array}{rlll} \sum \limits _{i | v_j \in D(X_i)} x_{ij} &{}\le &{} 1 &{} \qquad \forall v_j \in \bigcup ^{n}_{i=1} D(X_i)\\ \sum \limits _{v_j \in D(x_i)} x_{ij} &{}=&{} 1 &{} \qquad \forall i \in \{1,\ldots ,n\}\\ x_{ij}&{} \in &{}\{0,1\}&{} \qquad \forall i \in \{1,\ldots ,n\}, \forall v_j \in D(X_i) \\ \end{array} \right. \end{aligned}$$

(4)

A related global constraint is the $\textsc {GlobalCardinality}$ constraint [20]. It enforces the number of occurrences of each value $v_j$ to be at least $l_j$ and at most $u_j$ in the set $X_1,\ldots , X_n$ of variables. The formulation $\mathcal{F}$ is the following:

$$\begin{aligned} \mathcal{F} = \left\{ \begin{array}{rlll} \sum \limits _{i | v_j \in D(X_i)} x_{ij} &{}\le &{} u_j &{} \qquad \forall v_j \in \bigcup ^{n}_{i=1} D(X_i)\\ \sum \limits _{i | v_j \in D(X_i)} x_{ij} &{}\ge &{} l_j &{} \qquad \forall v_j \in \bigcup ^{n}_{i=1} D(X_i)\\ \sum \limits _{v_j \in D(x_i)} x_{ij} &{}=&{} 1 &{} \qquad \forall i \in \{1,\ldots ,n\}\\ x_{ij}&{} \in &{}\{0,1\}&{} \qquad \forall i \in \{1,\ldots ,n\}, \forall v_j \in D(X_i) \end{array} \right. \end{aligned}$$

(5)

$\mathcal{F}$ has the integrality property since the matrix can be seen as a specific case of a network flow matrix. Let us denote by $d = \max ^{n}_{i = 1} |D(X_i)|$, the maximum cardinality of the domains and $m = |\bigcup ^{n}_{i=1} D(X_i)|$, the total number of distinct values. Both formulations given have O(nd) variables and $O(n+m)$ constraints. Arc consistency can thus be established by solving the program $(P')$ which has twice the number of variables and $O(nd + m)$ constraints. Recall that the dedicated algorithms for each constraint respectively runs in $O(n^{1.5}d)$ for the $\textsc {AllDifferent}$, $O(n^2m)$ for the $\textsc {GlobalCardinality}$ and are incremental down a branch of the search tree.

5.2 The Family of Sequence Constraints

The Sequence constraint restricts the number of occurrences of some given values in any sequence of k variables. It can be expressed as a conjunction of Among constraints and has been used for car sequencing [5] and nurse rostering [7]. More precisely, $\textsc {Among}(l, u, \langle X_1,\ldots , X_k \rangle , V)$ holds if and only if $l \le |\{i |X_i \in V\}| \le u$. In other words, at least l and at most u of the variables take their values in the set V. The Sequence constraint can be defined as a conjunction of sliding Among constraints over k consecutive variables. $\textsc {Sequence}(l,u,k, \langle X_1, \ldots , X_n\rangle , V)$ holds if and only if $\forall i \in \{1,\ldots ,n-k+1\}$ $\textsc {Among}(l,u, \langle X_i, \ldots , X_{i+k-1}\rangle , V)$ holds.

An incomplete filtering algorithm for Sequence is proposed in [4]. Two arc consistency algorithms are later given in [24, 25] with respective running times of $O(n^3)$ and $O(2^kn)$. Additionally, an encoding achieving arc consistency is presented in [7] and runs in $O(n^2log(n))$ down a branch of a search tree. It is latter improved in [13] by using the fact that a natural integer programming formulation of the constraint has the consecutive ones property on the columns. This is used to build a network flow graph and derive an arc consistency algorithm. The complexity of this flow-based propagator to enforce arc consistency is $O(n((n-k)(u-l)+u))$ when using the Ford-Fulkerson algorithm for finding a maximum flow. The incremental cost when fixing a single variable is only O(n) so that the algorithm runs in $O(n^2)$ down a branch of a search tree.

A generalization of Sequence is known as Gen-Sequence and allows different occurrences (l and u) and sizes (k) for an arbitrary set of m Among constraints over consecutive variables. $\textsc {Gen-Sequence}(p_1, \ldots , p_m, \langle X_1, \ldots , X_n \rangle , V)$ holds if and only if $\forall \, 1 \le i \le m$, $\textsc {Among}(l_i,u_i,\langle X_{s_i}, \ldots , X_{s_i+k_i-1}\rangle , V)$ holds where $p_i = \{l_i, u_i, k_i, s_i\}$.

The Gen-Sequence global constraint is defined in [24, 25] and a $O(n^4)$ algorithm is proposed to enforce arc consistency. The consecutive one property does not hold in general for a Gen-Sequence constraint. Although it may sometimes be possible to re-order the lines of the matrix to have the consecutive one property on the columns or to find an equivalent network matrix, [13] outlines that not all Gen-Sequence constraints can be expressed as network flows. The flow-based algorithm for Sequence can therefore not be reused in general. Nonetheless, the encoding of Sequence proposed in [7] extends to Gen-Sequence and runs in $O(nm+n^2\log n)$ [13]. Finally, in [3], a filtering method based on unit propagation over a conjunctive normal form encoding of the constraint is proposed and achieves arc consistency in $O(mn^3)$.

Notice that the previous sequence constraints can be encoded with a simple boolean channeling, without hindering any filtering since the resulting constraint network is Berge-acyclic. Typically $\textsc {Gen-Sequence}(p_1, \ldots , p_m, \langle X_1, \ldots , X_n \rangle , V)$ can be stated as:

$$\begin{aligned} \left\{ \begin{array}{rr} \textsc {Gen-Sequence}(p_1, \ldots , p_m,\langle Y_1, \ldots , Y_n \rangle , 1) \\ Y_i = 1 \Leftrightarrow X_i \in V, \forall i \in \{1,\ldots ,n\} \\ Y_i \in \{0,1\}, \forall i \in \{1,\ldots ,n\} \end{array} \right. \end{aligned}$$

(6)

All previous studies thus focused on the restricted case where $V=\{1\}$. The integer linear formulation for $\textsc {Gen-Sequence}(p_1, \ldots , p_m,\langle Y_1, \ldots , Y_n \rangle , 1)$ is the following:

$$\begin{aligned} \mathcal{F} = \left\{ \begin{array}{rlll} \sum \limits ^{s_i+k_i-1}_{j=s_i} y_{j} &{}\le &{} u_i &{} \qquad \forall i \in \{1, \ldots , m\} \\ \sum \limits ^{s_i+k_i-1}_{j=s_i} y_{j} &{}\ge &{} l_i &{} \qquad \forall i \in \{1, \ldots , m\}\\ y_{j} &{}\in &{}\{0,1\}&{} \qquad \forall j \in \{1,\ldots ,n\} \end{array} \right. \end{aligned}$$

(7)

This formulation has the integrality property, as already mentioned in [13]. The linear program $(P')$ solved by the proposed LP-based procedure to enforce arc consistency has O(n) variables and $O(m + n)$ constraints. Recall that the best arc consistency algorithm for Gen-Sequence is the encoding of [13] and runs in $O(nm+n^2\log n)$.

6 Numerical Results

We carried out experiments on the AllDifferent and Sequence global constraints. The first set of experiments compares the LP-based filtering to the dedicated filtering algorithm of AllDifferent (Sect. 6.1). It also evaluates in practice the power of reduced-cost based filtering. The second one (Sect. 6.2) compares two encodings of Sequence to the LP-based filtering on random sequences alone following the experiments reported in [13]. Finally the last one evaluates the LP-based filtering on the Car-sequencing problem (Sect. 6.3).

The experiments were performed with Windows 8 on an Intel Core i5 @ 2.5 GHz with 12 GB of RAM. A memory limit of 4 GB of RAM was used. The indicators shown in the result tables are the average resolution time in seconds (CPU), the average number of nodes (N) and the average speed of the resolution in node per second (N/s). The constraint solver used is Choco 3.3 [16].

6.1 LP and Reduced-Cost Filtering for the AllDifferent constraint

The LP-based filtering is implemented for AllDifferent with the polytope given in Sect. 5.1. It is referred to as AllDifferentLPF (for LP Filtering) and compared with three other filtering algorithms: the Choco AllDifferent constraint, the decomposition into cliques of difference constraints (DEC) and the reduced-cost based filtering algorithm in addition to the decomposition (RCF). As mentioned in Sect. 3, when filtering via reduced costs, the use of an objective function of the form cx can increase the chances of having non null reduced costs. To perturb the dual, the objective function used is $\sum _{i=1}^{n}{c_i (\sum _{j \in D(X_i)} x_{ij})}$, where the $c_i$ are randomly chosen in $[-10,10]$ at each node. Note that this function guarantees that all feasible solutions have the same cost.

We solve the QuasiGroup Completion problem [15]. The problem is to fill a n by n matrix previously filled at $k \%$ with numbers from 1 to n such that on each line and on each column, each number appears only once. We compare four models and look for the number of nodes needed to find all solutions for small instances with a lexicographic branching heuristic. Table 1 shows the average results on 10 randomly generated instances for each size $n \in \{5,10,15\}$. These three classes of instances are respectively filled at 10, 40 and 50% to have instances solvable under 3600 s. One instance with $n=15$ is solved within the time limit by Choco AllDifferent only and is thus not included in the results.

Table 1. QuasiGroup completion: filtering the AllDifferent constraint

As expected, AllDifferentLPF is slower than Choco AllDifferent that uses a dedicated algorithm. It is also on average three times slower than RCF. We can however see that it achieves arc consistency as it explores the same number of nodes than Choco AllDifferent. When $n=15$, RCF explores approximately twice the number of nodes of Choco AllDifferent or AllDifferentLPF. RCF does not achieve arc consistency, yet filters more than the decomposition alone. DEC propagates small constraints and is faster than RCF but can explore up to a 100 times the number of nodes of RCF for these instances.

6.2 Filtering One Sequence Constraint

The LP-based filtering is implemented for Sequence with the polytope given in Sect. 5.2. It is referred to as SequenceLPF and compared with an encoding of Sequence: the PS encoding presented in [7] which achieves arc consistency using a decomposition based on partial sums with $O(nk^2)$ constraints. Following the experimentation of [13] we generated 20 instances of a single sequence for each combination of $n \in \{500,1000,2000,3000,4000,5000\}$, $k \in \{5,15,50,75\}$ and $\varDelta = l-u \in \{1,5\}$. We look for the first solution found with a heuristic that randomly chooses the variable and the value to branch on. Figure 1 shows the evolution of the resolution time (in s) with the size of the instances.

Fig. 1.

Sequence

SequenceLPF is slower than the PS encoding on sequences with smaller k. However, when $k=75$, PS runs out of memory due to the number of constraints, whereas SequenceLPF can solve the sequence. Most importantly, as we can see on Fig. 1, LP filtering scales better with the problem: it does not seem very sensitive to the value of k.

6.3 The Car-Sequencing Problem

We evaluate the performance of SequenceLPF on the Car-sequencing problem [23]. The goal is to schedule n cars partitioned in k classes: the demand of a class c is denoted by $d_c$. Each class requires a subset of options in a set of m options. For each option j, there must be at most $p_j$ cars that require that option in each sub-sequence of size $q_j$. We consider the two first set of instances presented in [22]: Set 1 is composed of 70 feasible instances with 200 cars, Set 2 is composed of 4 feasible instances with 100 cars. All the instances are available in CSPLib. We use the model described by [22]: Variables

• The class variables are n integer variables $\mathcal{X}=\{X_1, \ldots , X_n\}$ taking their value in $\{1, \ldots ,k\}$. $X_i=c$ means that a car of class c is scheduled in slot i.

• The option variables are nm boolean variables $\mathcal{Y}=\{Y_{1,1}, \ldots , Y_{n,m}\}$. $Y_{i,j} = 1$ means that the car in slot i has the option j.

Constraints

• The demand constraint states that the demand of each class must be satisfied and is enforced by GlobalCardinality($\mathcal {X}$, $\{d_1, \ldots , d_k\}$), meaning that for each class $c \in [1,n]$ the number of variables in $\mathcal {X}$ taking the value c should be exactly $d_c$.

• The capacity constraints: for each option j, in each sub-sequence of cars of size $q_j$, the number of cars requiring option j is limited by $p_j$. For each option j, we set: Sequence($0, p_j, q_j, \{Y_{1,j}, \ldots , Y_{n,j}\}$).

• The option and class variables are linked using implication constraints. For each class c, we define $O_c$ the set of options required by the class. For each slot i, we set: $X_i = c \Rightarrow Y_{i,j} = 1 \, \, \forall \, j \in O_c$ and $X_i = c \Rightarrow Y_{i,j} = 0 \, \, \forall \, j \not \in O_c$.

The problem is to find a single feasible solution and the search is done with a branching heuristic defined in [22] denoted by . It branches lexicographically on the class variables and chooses the class for which the sum of the loads of each option is the highest. We set a time limit of 1200 s. Table 2 compares a model with the filtering of SequenceLPF to a model with the PS encoding. The columns CST and VAR show the average number of constraints and variables of the model.

Table 2. Car-sequencing Sets 1 and 2

The branching heuristic is very efficient for the first set of instances whereas only 1 instance out of the 4 of Set 2 is solved. The Sequence constraints are not very big ($n\le 200$ and $k\le 5$), hence PS has no more than 12000 constraints and is faster than SequenceLPF. For this more complex problem, LP filtering is only 20 times slower than the encoding that achieves arc consistency while for QuasiGroup Completion, it is 100 times slower than the Choco AllDifferent constraint.

7 Conclusion and Future Work

Given a formulation of a constraint with the integrality property, we have shown that arc consistency can be achieved by solving a single linear program. We believe it is very useful to provide arc consistency algorithms for numerous polynomial constraints that are not available in solvers. Although it is unlikely to be competitive with dedicated and incremental filtering algorithms, a number of improvements have yet to be investigated. Firstly, the algorithm boils down to the search for an interior point in a polytope and there might be more efficient techniques, although maybe more difficult to implement, than the simplex algorithm for that purpose. Secondly, the result itself is more general than the specific usage done here to enforce arc consistency since it can be used to detect integer variables necessarily grounded to a bound of their domain. This raises the question whether more sparse LP formulations that does not necessarily introduce a variable per value of the original domains can be used. Finally, polynomial constraints with high running times often have a cost variable, for instance the MinimumWeightAlldifferent, so that a natural extension of this work is to handle an objective function.