Continuous and Binary Variables Constraints Satifiability

Binary Constraint

Handbook of Constraint Programming

Rina Dechter , in Foundations of Artificial Intelligence, 2006

Example 7.17.

Consider the binary constraint problem whose primal graph appears in Figure 7.8(a). The join-trees in Figure 7.9(a) and (b) were obtained via triangulation in orderings of Figure 7.8band 7.8c and can be redescribed in Figure 7.10, using the two labeling functions. The X labelings are the sets inside each node.

Figure 7.10. Two tree-decompositions

Once a tree-decomposition is available, algorithm Cluster-Tree Elimination (CTE) in Figure 7.11, can processes the decomposition. The algorithm is presented as a message-passing algorithm, where each vertex of the tree sends a constraint to each of its neighbors. If the tree contains m edges, then a total of 2m messages will be sent. Node u takes all the constraints in ψ(u) and all the constraint messages received by u from all adjacent nodes, and generate their join projected on the various separators with its neighbors. The resulting constraint is then sent to v (remember that v is adjacent to u in the tree).

Figure 7.11. Algorithm cluster-tree elimination (CTE)

Implementing Equation 7.1: The particular implementation of equation (7.1) in CTE can vary. One option is to generate the combined relation ( ${\bowtie }_{R_i\in duste{r}_v(u)}{R}_i$ ) before sending messages to neighbor v. The other option, which we assume here, is that the message sent to each neighbor is created without recording the relation ( ${\bowtie }_{R_i\in duste{r}_v(u)}{R}_i$ ). Rather, each tuple in the join is projected on the separator immediately after being created. This will yields a better memory utilization. Furthermore, when u sends a message to v its cluster may contain the message it received from v. Thus in a synchronized message passing we can allow a single enumeration of the tuples in cluster (u) when the messages are sent back towards the leaves, each of which be projected in parallel on the separators of the outgoing messages.

The output of CTE is the original tree-decomposition where each node is augmented with the constraints sent to it from neighboring nodes, called clusters. For each node the augmented set of constraints is a minimal subproblem relative to the input constraint problem R. Intuitively, a subproblem of a constraint network is minimal if one can correctly answer any query on it without having to refer back to information in the whole network. More precisely, a subproblem over a subset of variables Y is minimal relative to the whole network, if its set of solutions is identical to the projection of the networks' solutions on Y.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S1574652606800118

Handbook of Constraint Programming

David Cohen , Peter Jeavons , in Foundations of Artificial Intelligence, 2006

Example 8.9.

The class of binary constraints known as connected row-convex constraints was introduced in [35] and shown to be tractable. This class properly includes the 'monotone' relations, identified and shown to be tractable by Montanari in [76].

Let the domain D be the ordered set {d ₁,d ₂,…,d_m}, where $d_1<d_2<\mathrm{\dots }<dm$ . The definition of connected row-convex constraints given in [35] uses a standard matrix representation for binary relations: the binary relation R over D is represented by the m × m 0−1 matrix M, by setting M _ij = 1 if the relation contains the pair 〈d_i ,d_j 〉, and M _ij = 0 otherwise.

A relation is said to be connected row-convex if the following property holds: the pattern of 1's in the matrix representation (after removing rows and columns containing only 0's) is connected along each row, along each column, and forms a connected 2-dimensional region (where some of the connections may be diagonal).

By [35] we see that the following examples of connected row-convex relations:

$\begin{array}{ccc}\left(\begin{array}{l}0000010000\\ 0000111000\\ 0001111010\\ 0111111010\\ 1111111011\\ 0111111010\\ 0011111010\\ 0011111010\\ 0001100000\\ 0000100000\end{array}\right)& \left(\begin{array}{l}1100000000\\ 1100000000\\ 0011100000\\ 0011100000\\ 0011100000\\ 0011100000\\ 0000011111\\ 0000011111\\ 0000011100\\ 0000011100\end{array}\right)& \left(\begin{array}{l}0000000100\\ 0000001100\\ 0000000000\\ 0000001111\\ 0000001110\\ 0000110000\\ 0000100000\\ 1111000000\\ 0111000000\\ 0011000000\end{array}\right)\end{array}$

form a tractable constraint language.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S157465260680012X

Handbook of Constraint Programming

Barbara M. Smith , in Foundations of Artificial Intelligence, 2006

11.8.1 Non-Binary to Binary translations

Early search algorithms for CSPs only dealt with binary constraints; as a result, there are some standard transformations of a CSP with non-binary constraints into a binary CSP [ 1]. The hidden variable transformation adds a new variable h_i to the CSP for each non-binary constraint, c_i ; the values of h_i correspond to tuples of variables in the scope of c_i . The original constraint c_i is replaced by binary constraints between h_i and the variables in the scope of c_i ; each value of h_i implies a value for each variable in the scope of c_i , and the binary constraints enforce this correspondence. In the terminology of this chapter, the hidden variables would be classed as auxiliary variables, rather than a change of viewpoint.

The dual graph translation of a non-binary CSP replaces the original constraints by new variables, and so produces a new CSP based on a different viewpoint. The dual variable d_i represents the constraint c_i , and its values represent the tuples satisfying c_i . There is a binary constraint between two dual variables d_i and d_j if the scopes of c_i and c_j have a non-empty intersection; the binary constraint forbids pairs of values which would assign different values to any of the shared variables.

Bacchus and van Beek [1] investigate these transformations empirically, using a forward checking algorithm: when applied to the original non-binary model, the algorithm checks a k-ary constraint whenever all but one variable in its scope has been assigned. They show that both the hidden variable and dual graph transformation can outperform the original model; however, given constraint solvers that have better ways of dealing with many types of non-binary constraint, these transformations have been little used in practice.

An exception is the use of dual variables to replace 9-ary constraints in the Maximum Density Still Life problem, described earlier in Section 11.5.4. In [42], the 9-ary constraints between a cell and its eight neighbours are replaced by dual variables, exactly as in the dual graph transformation. Unlike the dual graph transformation, the original variables are also kept, although only in order to express the objective, that the number of live cells should be maximized. The dual variables represent 3 × 3 'supercells'; one advantage of the dual graph translation, as well as replacing the cumbersome 9-ary constraints, is that it allows the supercells rather than the cells to be the search variables. Hence, the dual graph translation in this case corresponds to a genuinely different perspective on the problem.

A similar transformation has been used by Hnich, Prestwich and Selensky [25] in modelling the covering test problem (problem 45 in CSPLib), arising in software testing. The covering test problem is: for a given tuple (t, k, g, b) find a covering array CA(t, k, g) of size b or show that none exists. The covering array has k columns and b rows, and in every subset of t columns every possible t-tuple over the alphabet Z_g = {0, 1, 2, …, g – 1} must occur in at least one row. A solution for t = 3, k = 5, g = 2, b = 10 is shown in Figure 11.2. Every triple of values from {0, 1}, from (0,0,0) to (1,1,1), occurs in the first three columns of the array, and this is true of every other subset of three columns as required.

Figure 11.2. A covering array CA(3, 5, 2) of size 10.

A natural way to model the problem is to introduce a b × k matrix of integer variables, x_ri , for 1 ≤ r ≤ b and 1 ≤ i ≤ k, such that x_ri = m if the value in column i and row r of the array is m. However, it is hard to express the constraints that in every subset of t columns, every possible t-tuple must occur.

To make these constraints easier to express, Hnich et al. introduced compound variables, analogous to the variables of the dual graph transformation, to represent every t-tuple of columns in each row. In the case of a binary alphabet, each compound variable has domain {0, …, 2 ^t }. There are still non-binary constraints on these variables: there is a global cardinality constraint on the compound variables corresponding to a given t-tuple in each row, to ensure that every value between 0 and 2 ^t – 1 is assigned at least once. In addition, just as in the dual graph translation, there are binary constraints between the compound variables corresponding to a row that if they have columns in common, in terms of the original variables, they must agree on the values that they give to their shared variables.

These examples show that the dual variables of the dual graph translation can be practically useful in rewriting non-binary constraints, even without eliminating the non-binary constraints completely.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S1574652606800155

Directional Consistency

Rina Dechter , in Constraint Processing, 2003

4.2.4 Graph Aspects of Directional Consistency

Neither directional arc-consistency nor full arc-consistency can change the constraint graph. Higher levels of directional consistency do change the constraint graph, although to a lesser extent than their nondirectional counterparts. For example, applying dpc to the network whose ordered graph is given in Figure 4.8(a) results in a network having the graph in Figure 4.8(b), where arc (x ₁, x ₃) is added. If we apply dpc to the problem in Figure 4.6, no constraint will be added, since the changes are only those caused by arc-consistency. Full path-consistency, on the other hand, will make the constraint graph of Figure 4.6 complete. Before continuing with this section, you should refresh your memory of the graph concepts defined in Section 4.1, if necessary.

During processing by dpc, a variable x _k only affects the constraint between a pair of earlier variables when it is constrained via binary constraints ¹ and is thus connected to both earlier variables in the graph. In this case, a new constraint and a corresponding new arc may be added to the graph. Algorithm dpc recursively connects the parents of every two nodes in the ordered constraint graph, thus generating the induced ordered graph. Indeed, the graph in Figure 4.8(b) is the induced graph of the ordered graph in Figure 4.8(a).

PROPOSITION 4.5

Let (G, d) be the ordered constraint graph of a binary network R. If DPC is applied to R relative to order d, then the graph of the resulting constraint network is subsumed by the induced graph (G ^*, d).

Proof

Let G be the original constraint graph of R, and let G ₁ be the constraint graph of the problem generated by applying dpc to R along d. We prove the above claim by induction on the variables along the reverse ordering of d = (x ₁,…, x _n ). The induction hypothesis is that all the arcs incident to x _n ,…, x _i in G ₁ appear also in (G ^*, d). The claim is true for x _n (the induction base step), since its connectivity is equivalent in both graphs. Assume that the claim is true for x _n ,…, x _i , and we will show that it holds also for i − 1 (i.e., for x _n ,…, x _i-1). Namely, we will show that if (x _i-1, x _j ), j < i − 1, is an arc in G ₁, then it is also in (G ^*, d). There are two cases: either x _i-1 and x _j are connected in G ₁ (i.e., they have a binary constraint in R, and therefore they will stay connected in (G ^*, d)), or a binary constraint over {x _i-1, x _j } was added by dpc. In the second case, this new binary constraint was obtained while processing some later variable x _t , t > i − 1. Since a constraint over x _i-1 and x _j is generated by dpc, both x _j and x _i-1 must be connected to x _t in G ₁ and, following the induction hypothesis, each will also be connected to x _t in (G ^*, d). Therefore, x _i-1 and x _j will become connected when generating the induced graph (G ^*, d) (i.e., when connecting the parents of x _t ).

The induced graph and its induced width can be used to refine the worst-case complexity of dpc along d. Since dpc processes only pairs of variables selected from the set of current parents in the ordered constraint graph, the number of such pairs can be bounded by the parent set size of each variable, namely, by w ^*(d). We conclude the following:

THEOREM 4.2

Given a binary network R and an ordering d, the complexity of dpc along d is O((w ^*(d))² · n · k ³), where w ^*(d) is the induced width of the ordered constraint graph along d.

Proof

Proposition 4.5 asserts that when a variable x is being processed by dpc it is connected to at most w ^*(d) parents. Therefore the number of triplets that a variable can share with its parents is O(w ^*(d)²). Since processing each triplet is O(k ³), and since there are n variables altogether, we get the complexity bound claimed above.

Consequently, orderings with a small induced width allow dpc to be more efficient. Rather than being governed by cubic complexity, dpc is linear in the number of variables for networks whose constraint graph has bounded induced width.

The complexity of general dic _i can be bounded using the induced width as well. Given a general network whose constraint scopes are bounded by i, applying dic _i in any ordering connects the parents of every node in the ordered primal constraint graph (restricted to constraints of arity i or less), yielding again its induced graph. We can now extend Proposition 4.5 and Theorem 4.2 to the general i-consistency case.

PROPOSITION 4.6

Given a network R whose constraint arity is bounded by i, if dic _i is applied to R relative to order d, then the primal graph of the resulting constraint network is subsumed by the induced graph (G ^*, d).

Proof

See Exercise 8.

The complexity of the algorithm is determined by the revise procedure. If the algorithm records a constraint on a set of size j, its complexity is O((2k) ^j ). Since the size of the parent set is bounded by w ^*(d), and the number of its subsets of size i is bounded by O((w ^*(d)) ⁱ ), we conclude the following:

THEOREM 4.3

Given a general constraint network R whose constraints' arity is bounded by i, and an ordering d, the complexity of dic _i along d is O(n(w ^*(d)) ⁱ . (2k) ⁱ ).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9781558608900500050

Handbook of Constraint Programming

Carla Gomes , Toby Walsh , in Foundations of Artificial Intelligence, 2006

18.1.5 Flaws and Flawless Methods

Random problems may contain structures which make them artificially easy. One issue is trivial flaws which a polynomial algorithm could easily discover. In a binary constraint satisfaction problem, the assignment of a value to a variable is said to be flawed if there exists another variable that cannot be assigned a value without violating a constraint. The value is supported otherwise. A variable is flawed iff each value is flawed. A problem with a flawed variable cannot have a solution. Achlioptas et al. [ 4] identify a potential shortcoming of all four random models. They prove that if p ₂ ≥ 1/m then, as n goes to infinity, there almost surely exists a flawed variable. Such problems are not intrinsically hard as a simple arc-consistency algorithm can solve them in polynomial time.

Fortunately, such flaws are unlikely in the size of problems used in practice [27]. We can also define parameters for existingmethods and new generationmethods which prevent flaws. For example:

model B: the parameter scheme m = n ^α, p ₁ = β log(n)/(n – 1) for some constants α, β [91, 89]; Xu and Li also present a similar parameter scheme for model D in which domain size grows polynomially with the number of variables; such problems are guaranteed to have a phase transition and to give problems which almost surely have an exponential resolution complexity;

model D: Smith proposes a somewhat more complex scheme which increases m and the average degree of the constraint graph with n [81];

model E: a new generation method in which we select uniformly, independently and with repetition, exactly pm ² n(n – 1)/2 nogoods out of the m ² n(n – 1)/2 possible for some fixed p [4];

modified models A to D: we ensure the conflict matrix of each constraint is flawless by randomly choosing a permutation π _i of 1 to m, and insist that (i, π _i ) is a good before we randomly pick nogoods from the other entries in the conflict matrix; each value is thereby guaranteed to have some support [27].

Model E is very similar to the one studied by Williams and Hogg [86]. One possible shortcoming of Model E is that it generates problems with a complete constraint graph for quite small values of p. It is hard therefore to test the performance of algorithms on sparse problems using Model E [27].

The modified versions of models A to D are guaranteed not to contain trivial flaws which would be uncovered by enforcing arc-consistency. However, more recent results have shown that such problems may still be asymptotically unsatisfiable and can be solved in polynomial time using a path consistency algorithm [25]. In response, Gao and Culberson propose a method to generate random problems which are weakly path-consistent, and which almost surely have an exponential resolution complexity.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S1574652606800222

Temporal Constraint Networks

Rina Dechter , in Constraint Processing, 2003

12.2.4 Network-Based Algorithms

As with general constraint satisfaction problems, temporal constraint networks may potentially exploit the topology of their constraint graphs. However, since temporal networks allow only binary constraints, they can only exploit structures having induced width of 1 or 2, or tree decompositions whose separator size is 1 or 2. The former corresponds to the case of nonseparable components. Applying a general tree decomposition algorithm, however, is not natural since it requires enforcing constraints of larger scopes, which are not in the language of binary temporal networks. Moreover, the idea of cycle-cutset cannot be employed beneficially in quantitative temporal problems because the backtracking used in the solution of TCSPs instantiates arcs, rather than variables, and such instantiations do not decompose the original network in the same way.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978155860890050013X

Handbook of Constraint Programming

Ian P. Gent , ... Jean-François Puget , in Foundations of Artificial Intelligence, 2006

Theorem 10.24. [101]

Given a CSP with n variables V, such that there exists an all-different constraint on these variables, then all variable symmetries can be broken by at most n – 1 binary constraints.

For our example, we get exactly 5 constraints: notice this is n – 1 in this case.

$A<B,A<D,A<E,A<F,B<C$

While this is only a reduction of a single constraint, that is simply because of the small size of the example. In general, Puget has reduced the number of symmetries required from a possibly n! to as little as n – 1, for the commonly occurring case of variable symmetries in the presence of an all-different constraint. As well as its value in its own right, this shows the power of combining symmetry breaking constraints with constraints from a problem, and this remains an area ripe for exploitation.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S1574652606800143

European Symposium on Computer Aided Process Engineering-12

V. Bansal , ... S. de Wolf , in Computer Aided Chemical Engineering, 2002

5 Solution and Results

(8) corresponds to a MIDO problem with 509 differential equations, 8295 algebraic equations (not including the 20,000 or so physical properties equations), 475 end-point inequalities, 32 pure binary constraints, 9 continuous search variables and 60 binary search variables. This formidably-sized problem was solved using the MIDO algorithm described in Chapter 6 of Bansal (2000). This algorithm has already been used to solve industrial-type problems (Chapter 7 of Bansal, 2000 and Bansal et al., 2000b). In this study, gPROMS vl.8.4 (Process Systems Enterprise Ltd, 2000) was used to solve the primal problems and GAMS v2.5/CPLEX (Brooke et al., 1992) was used to solve the master problems.

Using a termination tolerance of ε = 0, the MIDO algorithm converged in just 8 iterations and was able to find three structures that are cheaper than the original structure considered in the study of Ross et al. (1999, 2001). The optimal solution was found on the fourth primal solution, and as shown in Table 1, its total annualised cost is 18% less than the existing Shell design. These savings are achieved by removing more NPA from the IPA column (increased draw-off rate) so that the IPA column capacity can be significantly reduced (smaller diameter and reboiler duty). Although the capacity and hence cost of the NPA column increase, the savings in the cost of IPA column easily outweigh this.

Table 1. Comparison of the Design obtained via MIDO with the Existing Design.

Design Variable	Optimal Design using MIDO	Existing Design
Draw-off Location	18	22
Feed Location	8	14
Qreb (IPA) (MW)	14.67	19.54
Dcol (IPA) (m.)	2.58	3.17
Draw (t/hr)	4.20	1.69
Return (t/hr)	3.43	1.20
Qreb (NPA) (MW)	2.45	0.87
Dcol (NPA) (m.)	1.33	0.87
Capital Cost ($M yr-1 )	0.56	0.63
Operating Cost ($M yr-1 )	3.56	4.37
Total Cost	4.12	5.00

Figure 2 plots the mass fraction of NPA in the IPA/water azeotrope product for the optimally designed system. It can be seen that the constraint that the mass fraction is less than 800   ppm is satisfied at all times during operation. Other plots like this one are automatically given as part of the MIDO solution. Note that Figure 2 shows the dynamic operation over one week, which is more than ten times longer than the 15 hr. time horizon that was used for solving the primal dynamic optimization problems. The cyclical behaviour and the fact that the constraint is never violated thus suggest that the optimally designed process and control system is also stable.

Figure 2. Mass Fraction of NPA in the Azeotrope Product.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S1570794602800554

PROPOSITIONAL SATISFIABILITY AND CONSTRAINT SATISFACTION

Holger H. Hoos , Thomas Stützle , in Stochastic Local Search, 2005

Prominent Benchmark Instances for the CSP

There are numerous types of CSP instances that have been commonly used in the literature on the CSP. Many studies have focused on a particular class of randomly generated CSP instances with binary constraint relations, which we call Uniform Random Binary CSP. Besides the number of CSP variables and the size of the variable domains, this problem distribution is characterised by two parameters, the constraint graph density α and the constraint tightness β; α specifies the probability that a constraint relation exists between an arbitrary pair of CSP variables, and β is the expected fraction of value pairs that satisfy a given constraint relation. For this class of CSP instances, a solubility phase transition phenomenon with an associated peak in hardness, similar to the one for Uniform Random 3-SAT, has been observed [Smith, 1994], and test-sets of hard instances can be obtained for specific combinations of α and β values.

Another widely used class of CSP instances stems from the Graph Colouring Problem (see Example 6.2), which can be seen as a special case of the finite discrete CSP in which all variables have the same domain, and all constraint relations are binary, allowing a pair of values (x, y) if, and only if, x ≠ y (inequality constraint). The Graph Colouring Problem and specific instance classes are discussed in more detail in Chapter 10, Section 10.1. Graph colouring instances with three colours are amongst the most commonly used benchmark instances for the CSP.

A prominent special case of the Graph Colouring Problem is the Quasigroup Completion Problem (QCP), which is derived from the following Quasigroup Problem or Latin Square Problem: Given an n × n quadratic grid and n colours, the objective is to assign a colour to each grid cell in such a way that every row and column contains all n colours. In the QCP, the objective is to decide whether a partial solution of the Quasigroup Problem, that is, an incomplete assignment of colours to the given grid such that no two cells in the same row or column have the same colour, can be extended into a complete solution by assigning colours to the remaining cells. In the CSP formulation, the pre-assigned cells can be easily represented by unary constraints. The QCP is known to be $\mathcal{N}\mathcal{P}$ -complete [Colbourn, 1984], and a phase-transition phenomenon with an associated peak in hardness has been observed [Gomes and Selman, 1997b]. The QCP has a variety of important applications in areas, such as dynamic wavelength routing in fibre optic networks and the design of statistical experiments [Kumar et al., 1999; Laywine and Mullen, 1998].

The n-Queens Problem is another prominent CSP; it can be seen as a generalisation of the problem of placing eight queens on a chessboard such that no queen is threatened by any of the other queens. This is achieved by distributing the queens in such a way that no row, column, or diagonal has more than a single queen on it. The 8-Queens Problem can be represented as a CSP instance with 8 variables and 28 binary constraints. In the n-Queens Problem, the objective is to place n queens on an n × n board subject to analogous constraints.

Most of the work on CSP has been focused on binary CSP. One of the reasons for this is that any non-binary CSP instance can be transformed into a binary CSP instance in a rather straight-forward way [Dechter and Pearl, 1989; Rossi et al., 1990; Bacchus et al., 2002]. Another reason lies in the fact that algorithms restricted to binary CSP instances are typically easier to implement than general CSP solvers.

There are numerous other classes of CSP instances, including CSP encodings of the real-world problems mentioned in Section 6.1. Some application-relevant problems include frequency assignment in radio networks, scheduling problems and vehicle routing. A description of many of the different types of constraint satisfaction problems can be found at CSPLIB, a benchmark library for constraints [Gent et al., 2003].

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9781558608726500238

Constraint Search

Stefan Edelkamp , Stefan Schrödl , in Heuristic Search, 2012

13.2 Consistency

Consistency is an inference mechanism to rule out certain variable assignments, which in turn enhances the search. The simplest consistency check tests a current assignment against the set of constraints. Such a simple consistency algorithm for a set of assigned variables and a set of constraints is provided in Algorithm 13.1. We use Variables(c) to denote the set of variables that are mentioned in the constraint c, and Satisfied(c, L) to denote if the constraint c is satisfied by the current label set L(assignment of values to variables).

In the following we introduce more powerful inference methods like arc consistency and path consistency, and discuss specialized consistency techniques like the all-different constraint.

13.2.1 Arc Consistency

Arc consistency is one of the most powerful propagation techniques for binary constraints. For every value of a variable in the constraint we search for a supporting value to be assigned to the other variable. If there is none, the value can safely be eliminated. Otherwise, the constraint is arc consistent.

Definition 13.2

(Arc Consistency) The pair (X, Y) of constraint variables is arc consistent if for each value $x\mathfrak{\in }{D}_X$ there exists a value $y\mathfrak{\in }{D}_y$ such that the assignments X = x and Y = y satisfy all binary constraints between X and Y. A CSP is arc consistent if all variable pairs are arc consistent.

Consider a simple CSP with the variables A and B subject to their respective domains $D_A=\mathfrak{\{}1,2\mathfrak{\}}$ and $D_B=\mathfrak{\{}1,2,3\mathfrak{\}}$ , as well as the binary constraint A < B. We see that value 1 can be safely removed from D_B based on constraint and the restriction we have on A.

Algorithm 13.1. Simple consistency algorithm.

In general, constraints are used actively to remove inconsistencies from the problem. An inconsistency arises if we arrive at a value that cannot be contained in any solution. To abstract from different inference mechanisms we assume a procedure Revise, to be attached to each constraint, which governs the propagation of the domain restrictions.

AC-3 and AC-8

Algorithm AC-3 is one option to organize and perform constraint reasoning for arc consistency. The input of the algorithm are the set of variables V, the set of domains D, and the set of constraints C.

In the algorithm, a queue of constraints is frequently revised. Each time, when the domain of a variable changes, all constraints over this variable are enqueued. The pseudo code of the approach is shown in Algorithm 13.2. As a simple example, take the following CSP with the three variables $D_X=D_Y=D_Z=\mathfrak{\{}1,2,3,4,5,6\mathfrak{\}}$ , subject to the binary constraints X < Y and Z < X − 2. As X < Y, we have $D_X=\mathfrak{\{}1,2,3,4,5\mathfrak{\}}$ , $D_Y=\mathfrak{\{}2,3,4,5,6\mathfrak{\}}$ , and $D_Z=\mathfrak{\{}1,2,3,4,5,6\mathfrak{\}}$ . Since Z < X − 2, we infer that $D_X=\mathfrak{\{}4,5\mathfrak{\}}$ , $D_Y=\mathfrak{\{}2,3,4,5,6\mathfrak{\}}$ , and $D_Z=\mathfrak{\{}1,2\mathfrak{\}}$ . Now we take constraint X < Y again to find the arc consistent set $D_X=\mathfrak{\{}4,5\mathfrak{\}}$ , $D_Y=\mathfrak{\{}5,6\mathfrak{\}}$ , and $D_Z=\mathfrak{\{}1,2\mathfrak{\}}$ . Snapshots of the algorithms after selecting variable c are provided in Figure 13.4.

Figure 13.4. Executing AC-3; Q is the queue of constraints, D_X the domain of variable X, and c the constraint selected.

Algorithm 13.2. Arc consistency with AC-3.

An alternative to AC-3 is to use a queue of variables instead of a queue of constraints. The modified algorithm is referred to as AC-8. It assumes that a user will specify, for each constraint, when constraint revision should be executed. The pseudo code of the approach is shown in Algorithm 13.3 and a step-by-step example is given in Figure 13.5.

Figure 13.5. Executing AC-8; Q is the queue of variables, D_X the domain of variable X, and v the variable selected.

13.2.2 Bounds Consistency

Arc consistency works well in binary CSPs. However, if we are confronted with constraints that involve more than two variables (e.g., X = Y + Z), the application of arc consistency is limited. Unfortunately, hyperarc consistency techniques are involved, and similar to the complexity of Set Covering and Graph Coloring-NP-hard for n ≥ 3. The problem is that we must determine which values of the variables are legitimate and which is a nontrivial problem.

The trick is to use an approximation of the set of possible assignments in the form of an interval. A domain range $D=\left[a,b\right]$ denotes the set of integers $\mathfrak{\{}a,a+1,\dots ,b\mathfrak{\}}$ with min _D = a and max _D = b.

Algorithm 13.3. Arc consistency with AC-8.

For bounds consistency we only look at arithmetic CSPs that range over finite-domain variables for which all constraints are arithmetic expressions. A primitive constraint is bounds consistent if for each variable X that is in the constraint there is an assignment for all other variables (in their domain range) that is compatible with setting X to min _D and X to max _D . An arithmetic CSP is bounds consistent if each primitive constraint is bounds consistent.

Consider the constraint X = Y + Z and rewrite it as X = Y + Z, Y = X − Z, and Z = X − Y. Reasoning about minimum and maximum values on the right side, we establish the following six necessary conditions: $X\ge {\min }_D\left(Y\right)+{\min }_D\left(Z\right)$ , $Y\ge {\min }_D(X)-{\max }_D(Z)$ , $Z\ge {\min }_D(X)-{\max }_D(Y)$ , $X\le {\max }_D(Y)+{\max }_D(Z)$ , $Y\le {\max }_D(X)-{\min }_D(Z)$ , and $Z\le {\max }_D(X)-{\min }_D(Y)$ . For example, the domains $D_X=\left[4..8\right]$ , $D_Y=\left[0..3\right]$ , and $D_Z=\left[2..2\right]$ are refined to $D_X=\left[4..5\right]$ , $D_Y=\left[2..3\right]$ , and $D_Z=\left[2..2\right]$ without missing any solution.

13.2.3 *Path Consistency

The good news about arc consistency is that it is fast in practice. The bad news is that arc consistency does not detect all inconsistencies. As a simple example consider the CSP shown in Figure 13.6 (left) with the three variables X, Y, Z with $D_X=D_Y=D_Z=\mathfrak{\{}1,2\mathfrak{\}}$ subject to X ≠ Y, Y ≠ Z, and X ≠ Z. The CSP is arc consistent but not solvable. Therefore, we introduce a stronger form of consistency.

Figure 13.6. A graph for which path consistency but not arc consistency is complete (left), and a graph for which path consistency is incomplete (right).

Definition 13.3

(Path Consistency) A path $\left(V_0,V_1,\dots ,V_m\right)$ is path consistent if, for all x in the domain of V₀, and for all y in the domain of V_m satisfying all binary constraints on V ₀ and V_m , there exists an assignment to $V_1,\dots ,V_{m-1}$ , s.t. all binary constraints between V_i and V_i+1 for $i\mathfrak{\in }\mathfrak{\{}0,\dots ,m-1\mathfrak{\}}$ are satisfied.

A CSP is path consistent, if every path is consistent.

This definition is long but not difficult to decipher. On top of binary constraints between two variables, path consistency certifies binary consistency between the variables on a path. It is not difficult to see that path consistency implies arc consistency. An example to show that path consistency is still incomplete is provided in Figure 13.6 (right).

For restricting the computational efforts, it is sufficient to explore paths of length two only (see Exercises). To come up with a path consistency algorithm, we consider the following example, consisting of the three variables A, B, C with D_A = D_B = D_C = {1, 2, 3}, subject to B > 1, A < C, A = B, and B > C − 2. Each constraint can be expressed in a (Boolean) matrix, denoting whether a variable combination is possible or not:

$B>1\sim \left(\begin{array}{c}\hfill 000\hfill \\ \hfill 010\hfill \\ \hfill 001\hfill \end{array}\right),A=B\sim \left(\begin{array}{c}\hfill 100\hfill \\ \hfill 010\hfill \\ \hfill 001\hfill \end{array}\right),A<C\sim \left(\begin{array}{c}\hfill 011\hfill \\ \hfill 001\hfill \\ \hfill 000\hfill \end{array}\right),B>C-2\sim \left(\begin{array}{c}\hfill 110\hfill \\ \hfill 111\hfill \\ \hfill 111\hfill \end{array}\right).$

Let R_i,j be the matrix entry for the constraint between variable i and j; R_k,k models the domain of k. Then consistency on the path (i, k, j) can be recursively determined by applying the equation

$R_{i,j}\leftarrow R_{i,j}\wedge \left(R_{i,k}{R}_{k,k}{R}_{k,j}\right).$

The concatenations correspond to Boolean matrix multiplications, such as the scalar product of the rows and columns in the matrix. The final conjunction is element-by-element.

For the example $R_{A,C}\leftarrow R_{A,C}\wedge R_{A,B}{R}_{B,B}{R}_{B,C}$ , we establish the following equation:

$\left(\begin{array}{c}\hfill 000\hfill \\ \hfill 010\hfill \\ \hfill 001\hfill \end{array}\right)\wedge \left(\begin{array}{c}\hfill 100\hfill \\ \hfill 010\hfill \\ \hfill 001\hfill \end{array}\right)\cdot \left(\begin{array}{c}\hfill 011\hfill \\ \hfill 001\hfill \\ \hfill 000\hfill \end{array}\right)\cdot \left(\begin{array}{c}\hfill 110\hfill \\ \hfill 111\hfill \\ \hfill 111\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 000\hfill \\ \hfill 001\hfill \\ \hfill 000\hfill \end{array}\right).$

We observe that path consistency restricts the set of possible instantiations in the constraint.

For a path-consistent CSP, we have to repeat the earlier revisions of paths. The pseudo code is shown in Algorithm 13.4. It is a straightforward extension to the All-Pairs Shortest Paths algorithm of Floyd and Warshall (see Ch. 2). Mathematically spoken, it is the same algorithm applied to a different semiring, where minimization is substituted by conjunction and addition is substituted by multiplication.

13.2.4 Specialized Consistency

As path consistency is comparably slow with respect to arc consistency, it is not always the best solution for overall CSP solving. In some cases specialized constraints (together with effective propagation rules) are often more effective.

One important specialized constraint is the all-different constraint (AD) that we already came across in the Sudoku and Cryptarithm domains at the beginning of this chapter.

Definition 13.4

(All-Different Constraint) The all-different constraint covers a set of binary inequality constraints among all variables X ₁ ≠ X ₂, X ₁ ≠ X ₃, …, X_k−1 ≠ X_k :

$AD\left(\mathfrak{\{}{X}_1,\dots ,X_k\mathfrak{\}}\right)=\mathfrak{\{}\left(d_1,\dots ,d_k\right)\mathfrak{|}\mathfrak{\forall }i:d_i\mathfrak{\in }{D}_i\wedge \mathfrak{\forall }i\ne j:d_i\ne d_j\mathfrak{\}}.$

Propagating the all-different constraint, we achieve strong pruning. Its efficient implementation is based on matching bipartite graphs, where the set of nodes V is partitioned into two disjoint sets V′ and V′′: for each edge its source and target nodes are contained in a different set, and a matching is a node-disjoint selection of edges.

Algorithm 13.4. Algorithm for path consistency.

The assignment graph for the all-different constraint consists of two sets. On one hand, we have the variables, and, on the other hand, we have the values that are in the domain of at least one of the variables. Any assignment to the variables that satisfies the all-different constraint is a maximum matching. The running time for solving bipartite matching problems in graph G = (V, E) is $O\left(\sqrt{\mathfrak{|}V\mathfrak{|}}\mathfrak{|}E\mathfrak{|}\right)$ (using maximum flow algorithms). An example for the propagation of the all-different constraint is provided in Figure 13.7.

Figure 13.7. Example of the all-different constraint for the variables {X,Y,Z,T} with D_X = {1,2}, and D_Y = {1,2}, D_Z = {1,2}, and D _T = {2,3,4,5}; matching edges (thick) show a selected assignment.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123725127000134

berrymakince.blogspot.com

Source: https://www.sciencedirect.com/topics/computer-science/binary-constraint

Share this post