On Broken Triangles

1 Introduction

At first sight one could assume that the discipline of constraint programming has come of age. On the one hand, efficient solvers are regularly used to solve real-world problems in diverse application domains while, on the other hand, a rich theory has been developed concerning, among other things, global constraints, tractable classes, reduction operations and symmetry. The research reported in this paper is part of a long-term project to bridge the gap between theory and practice.

Most research on tractable classes has been based on classes defined by placing restrictions either on the types of constraints or on the constraint hyper-graph whose vertices are the variables and whose hyper-edges are the constraint scopes. Another way of defining classes of binary CSP instances consists in imposing conditions on the microstructure, a graph whose vertices are the possible variable-value assignments with an edge linking each pair of compatible assignments [J´egou, 1993; Salamon and Jeavons, 2008]. If each vertex of the microstructure, corresponding to a variablevalue assignment hx↪ ai, is labelled by the variable x, then this so-called coloured microstructure retains all information from the original instance. The broken-triangle property Bruno Zanuttini GREYC Normandie University bruno.zanuttini@unicaen.fr

⇤ supported by ANR Project ANR-10-BLAN-0210. Martin Cooper was also supported by EPSRC grant EP/L021226/1.

(BTP) is a simple local condition on the coloured microstructure which defines a tractable class of binary CSP [Cooper et al., 2010]. Inspired by the BTP, investigation of other forbidden patterns in the coloured microstructure has led to the discovery of new tractable classes [Cohen et al., 2012; Cooper and Escamocher, 2015; Cooper and ˇZivn´y, 2012; El Mouelhi et al., 2015] as well as new reduction operations based on variable elimination [Cohen et al., 2015].

For simplicity of presentation we use two different representations of constraint satisfaction problems. In the binary case, our notation is fairly standard, whereas in the generalarity case we use a notation close to the representation of SAT instances. This is for presentation only, though, and our algorithms do not need instances to be represented in this manner.

Definition 1 A binary CSP instance I consists of

• ÷ a set X of n variables,
• ÷ a relation Rxy ✓ D(x)⇥D(y), for each pair of distinct variables x↪ y 2 X, which consists of the set of compatible pairs of values (a↪ b) for variables (x↪ y).
• ÷ a domain D(x) of values for each variable x 2 X,

A partial solution to I on Y = ¶y1↪ ▷ ▷ ▷ ↪ yr♦ ✓ X is a set ¶hy1↪ a1i↪ ▷ ▷ ▷ ↪ hyr↪ ari♦ such that 8i↪ j 2 [1↪ r], (ai↪ aj) 2 Ryiyj . A solution to I is a partial solution on X.

For simplicity of presentation, Definition 1 assumes that there is exactly one constraint relation for each pair of variables. An instance I is arc consistent if for each pair of distinct variables x↪ y 2 X, for each value a 2 D(x), there is a value b 2 D(y) such that (a↪ b) 2 Rxy.

In our representation of general-arity CSP instances, we require the notion of tuple which is simply a set of variablevalue assignments. For example, in the binary case, the tuple ¶hx↪ ai↪ hy↪ bi♦ is compatible if (a↪ b) 2 Rxy and incompatible otherwise.

Definition 2 A (general-arity) CSP instance I consists of

• ÷ a set X of n variables,
• ÷ a set NoGoods(I) consisting of incompatible tuples.
• ÷ a domain D(x) of values for each variable x 2 X,

A partial solution to I on Y = ¶y1↪ ▷ ▷ ▷ ↪ yr♦ ✓ X is a tuple t = ¶hy1↪ a1i↪ ▷ ▷ ▷ ↪ hyr↪ ari♦ such that no subset of t belongs to NoGoods(I). A solution is a partial solution on X.

z

2 Value merging in binary CSP

In this section we consider a method, based on the BTP, for reducing domain size while preserving satisfiability. Instead of eliminating a value, as in classic reduction operations such as arc consistency or neighbourhood substitution, we merge two values. We show that the absence of broken triangles on two values for a variable x in a binary CSP instance allows us to merge these two values in the domain of x while preserving satisfiability. This rule generalises the notion of virtual interchangeability [Likitvivatanavong and Yap, 2013] as well as neighbourhood substitution [Freuder, 1991].

It is known that if for a given variable x in an arc-consistent binary CSP instance I, the set of (in)compatibilities (known as a broken-triangle) shown in Figure 1 occurs for no two values a↪ b 2 D(x) and no two assignments to two other variables, then the variable x can be eliminated from I without changing the satisfiability of I [Cooper et al., 2010; Cohen et al., 2015]. In figures, each bullet represents a variable-value assignment, assignments to the same variable are grouped together within the same oval and compatible (incompatible) pairs of assignments are linked by solid (broken) lines. Even when this variable-elimination rule cannot be applied, it may be the case that for a given pair of values a↪ b 2 D(x), no broken triangle occurs. We will show that if this is the case, then we can perform a domain-reduction operation which consists in merging the values a and b.

Definition 3 Merging values a↪ b 2 D(x) in a binary CSP consists in replacing a↪ b in D(x) by a new value c which is compatible with all variable-value assignments compatible with at least one of the assignments hx↪ ai or hx↪ bi. A value-merging condition is a polytime-computable property P(x↪ a↪ b) of assignments hx↪ ai, hx↪ bi in a binary CSP instance I such that when P(x↪ a↪ b) holds, the instance I 0 obtained from I by merging a↪ b 2 D(x) is satisfiable if and only if I is satisfiable.

We now formally define the value-merging condition based on the BTP.

Definition 4 A broken triangle on the pair of variable-value assignments a↪ b 2 D(x) consists of a pair of assignments d 2 D(y), e 2 D(z) to distinct variables y↪ z 2 X ∩¶x♦ such that (a↪ d) ◁2 Rxy, (b↪ d) 2 Rxy, (a↪ e) 2 Rxz, (b↪ e) ◁2 Rxz and (d↪ e) 2 Ryz. The pair of values a↪ b 2 D(x) is BT-free if there is no broken triangle on a↪ b.

Proposition 5 In a binary CSP instance, being BT-free is a value-merging condition. Furthermore, given a solution to

✏

☞

✌

✏

☞

✍

✌

✍

✌

✏

☞

✏

☞

the instance resulting from the merging of two values, we can find a solution to the original instance in linear time.

Proof: Let I be the original instance and I 0 the new instance in which a,b have been merged into a new value c. Clearly, if I is satisfiable then so is I 0 . It suffices to show that if I 0 has a solution s which assigns c to x, then I has a solution. Let sa, sb be identical to s except that sa assigns a to x and sb assigns b to x. Suppose that neither sa nor sb are solutions to I. Then, there are variables y↪ z 2 X ∩ ¶x♦ such that ha↪ s(y)i ◁2 Rxy and hb↪ s(z)i ◁2 Rxz. By definition of the merging of a↪ b to produce c, and since s is a solution to I 0 containing hx↪ ci, we must have (b↪ s(y)) 2 Rxy and (a↪ s(z)) 2 Rxz. Finally, (s(y)↪ s(z)) 2 Ryz since s is a solution to I 0 . Hence, hy↪ s(y)i, hz↪ s(z)i, hx↪ ai, hx↪ bi forms a broken-triangle, which contradicts our assumption. Hence, the absence of broken triangles on assignments hx↪ ai, hx↪ bi allows us to merge these assignments while preserving satisfiability. Reconstructing a solution to I from a solution s to I 0 simply requires checking which of sa or sb is a solution to I. 2

The BTP-merging operation is not only satisfiabilitypreserving but, from Proposition 5, we know that we can also reconstruct a solution in polynomial time to the original instance I from a solution to an instance I m to which we have applied a sequence of merging operations until convergence. Indeed, we have the following stronger result [Cooper et al., 2014].

Proposition 6 Let I be a binary CSP instance and suppose that we are given the set of all solutions to the instance I m obtained after applying a sequence of BTP-merging operations. All N solutions to I can then be found in O(Nn2d) time.

The weaker operation of neighbourhood substitution has the property that two different convergent sequences of eliminations by neighbourhood substitution necessarily produce isomorphic instances I m 1 , I m 2 [Cooper, 1997]. This is not the case for BTP-merging. Firstly, and perhaps rather surprisingly, BTP-merging can have as a side-effect to eliminate broken triangles. This is illustrated in the instance shown in Figure 2. The instance in Figure 2(a) contains a broken triangle on values a0 , b0 for variable z, but after BTP-merging of values a↪ b 2 D(x) into a new value c, as shown in Figure 2(b), there are no broken triangles in the instance. Secondly, BTP-merging of two values in D(x) can introduce a

✏

☞

✍

✌

☞

✍

✌

Table 1: Results of experiments on CSP benchmark problems (Ninst = no. instances, Nval = no. values, Ndel = no. values deleted, Pdel = percentage deleted).

broken triangle on a variable z 6= x, as illustrated in Figure 3. The instance in Figure 3(a) contains no broken triangle, but after the BTP-merging of a↪ b 2 D(x) into a new value c, a broken triangle has been created on values a0 ↪ b0 2 D(z). Indeed, it has been shown that finding an optimal sequence of BTP-merges is NP-hard [Cooper et al., 2015].

3 Experimental trials

To test the utility of BTP-merging we performed extensive experimental trials on benchmark instances from the International CP Competition 1 . For each binary CSP instance, we performed BTP-mergings until convergence with a time-out of one hour. In total, we obtained results for 2,547 instances out of 3,811 benchmark instances within a time-out of one hour.

Table 1 gives a summary of the results of the experimental trials. We do not include those instances which are entirely solved by BTP-merging (such as all instances from the benchmark-domains hanoi and domino, or all instances from the pigeons benchmark-domain with a suffix -ord). We give details about those benchmark-domains where BTP-

1 http://www.cril.univ-artois.fr/CPAI08

✏

✏

✏

☞

☞

merging was most effective. All other benchmark-domains are grouped together in the last line of the table. The table shows the number of instances in the benchmark-domain, the average number of values (i.e. variable-value assignments) in the instances from this benchmark-domain, the average number of values deleted (i.e. the number of BTP-merging operations performed) and finally this average represented as a percentage of the average number of values.

We can see that for certain types of problem, BTP-merging is very effective, whereas for others (last line of the table) hardly any merging of values occurred. Runtime comparisons indicate that for BTP-merging to be useful in generalpurpose solvers, we need to develop efficient algorithms to target those instances in which many merges are likely to occur [Cooper et al., 2016].

4 BTP-merging: arbitrary-arity constraints

In the remainder of the paper, we assume that the constraints of a general-arity CSP instance I are given in the form described in Definition 2, i.e. as a set of incompatible tuples NoGoods(I), where a tuple is a set of variable-value assignments. For simplicity of presentation, we use the predicate Good(I↪ t) which is true iff the tuple t is a partial solution, i.e. t does not contain any pair of distinct assignments to the same variable and @t0 ✓ t such that t0 2 NoGoods(I). We first generalise the notion of broken triangle and merging to the general-arity case.

Definition 7 A general-arity broken triangle (GABT) on values a↪ b 2 D(x) consists of a pair of tuples t↪ u (containing no assignments to variable x) satisfying:

1. Good(I↪ t [ u) ^ Good(I↪ t [ ¶hx↪ ai♦) ^ Good(I↪ u [ ¶hx↪ bi♦)

The pair of values a↪ b 2 D(x) is GABT-free if there is no broken triangle on a↪ b.

Deciding whether a pair a↪ b is GABT-free is polytime for constraints given in extension (as the set of satisfying assignments) as well as for those given by nogoods (the set of assignments violating the constraint).

Definition 8 Merging values a↪ b 2 D(x) in a general-arity CSP instance I consists in replacing a↪ b in D(x) by a new value c which is compatible with all variable-value assignments compatible with at least one of the assignments hx↪ ai or hx↪ bi, thus producing an instance I 0 with the new set of nogoods defined as follows: NoGoods(I 0 ) =

A value-merging condition is a polytime-computable property P(x↪ a↪ b) of assignments hx↪ ai, hx↪ bi in a CSP instance I such that when P(x↪ a↪ b) holds, the instance I 0 is satisfiable if and only if I is satisfiable.

This merging operation can be performed in polynomial time whether constraints are represented positively in extension or negatively as nogoods. As in the binary case, absence of general-arity broken triangles allows merging [Cooper et al., 2014].

Proposition 9 In a general-arity CSP instance I, being GABT-free is a value-merging condition. Furthermore, given a solution to the instance resulting from the merging of two values, we can find a solution to I in linear time.

5 A tractable class of general-arity CSP

In binary CSP, the broken-triangle property defines an interesting tractable class when broken-triangles are forbidden according to a given variable ordering. Unfortunately, the original definition of BTP was limited to binary CSPs [Cooper et al., 2010]. Section 4 described a general-arity version of the broken-triangle property whose absence on two values allows these values to be merged while preserving satisfiability. An obvious question is whether GABT-freeness can be adapted to define a tractable class. We will see that this is possible for a fixed variable ordering, but not if the ordering is unknown.

Definition 7 defined a general-arity broken triangle (GABT). What happens if we forbid GABTs according to a given variable ordering? Absence of GABTs on two values a↪ b for the last variable x in the variable ordering allows us to merge a and b while preserving satisfiability. It is possible to show that if GABTs are absent on all pairs of values for x, then we can merge all values in the domain D(x) of x to produce a singleton domain. This is because merging a and b, to produce a merged value c, cannot introduce a GABT on c↪ d for any other value d 2 D(x). Once the domain D(x) becomes a singleton ¶a♦, we can clearly eliminate x from the instance, by deleting hx↪ ai from all nogoods, without changing its satisfiability. It is at this moment that GABTs may be introduced on other variables, meaning that forbidding GABTs according to a variable ordering does not define a tractable class.

Nevertheless, strengthening the general-arity BTP allows us to avoid this problem. The resulting directional generalarity version of BTP (for a known variable ordering) then defines a tractable class which includes the binary BTP tractable class as a special case.

We suppose given a total ordering < of the variables of a CSP instance I. We write t<x to represent the subset of the tuple t consisting of assignments to variables occurring before x in the order <, and V ars(t) to denote the set of all variables assigned by t.

Definition 10 A directional general-arity (DGA) broken triangle on assignments a↪ b to variable x in a CSP instance I is a pair of tuples t↪ u (containing no assignments to variable x) satisfying the following conditions:

1. t<x and u<x are non-empty
2. Good(I↪ t<x [ u<x ) ^ Good(I↪ t<x [ ¶hx↪ ai♦) ^ Good(I↪ u<x [ ¶hx↪ bi♦)
3. 9t0 s.t. V ars(t0 ) = V ars(t) ^ (t0 )<x = t<x ^ t0 [ ¶hx↪ ai♦ ◁2 NoGoods(I)
4. 9u0 s.t. V ars(u0 ) = V ars(u) ^ (u0 )<x = u<x ^ u0 [ ¶hx↪ bi♦ ◁2 NoGoods(I)

I satisfies the directional general-arity broken-triangle property (DGABTP) according to the variable ordering < if no directional general-arity broken triangle occurs on any pair of values a↪ b for any variable x.

Any instance I satisfying the DGABTP can be solved in polynomial time by repeatedly alternating the following two operations: (i) merge all values in the last remaining variable (according to the order <); (ii) eliminate this variable when its domain becomes a singleton. Both operations preserve satisfiability and neither of them can introduce DGA broken triangles [Cooper et al., 2014]. Moreover, the DGABTP can be tested in polynomial time for a given order.

Theorem 11 A CSP instance I satisfying the DGABTP on a given variable ordering can be solved in polynomial time.

An important question is the tractability of testing the existence of a variable ordering for which a given instance satisfies the DGABTP. Although this is polynomial-time for binary CSPs [Cooper et al., 2010], it turns out to be NP-hard for general-arity CSPs [Cooper et al., 2014].

Theorem 12 Testing the existence of a variable ordering for which a CSP instance satisfies the DGABTP is NP-complete.

6 Conclusion

This paper described a novel reduction operation for binary CSP, called BTP-merging, which is strictly stronger than neighbourhood substitution. Experimental trials have shown that in several benchmark-domains applying BTP-merging until convergence can significantly reduce the total number of variable-value assignments. We gave a general-arity version of BTP-merging and we then went on to define a general-arity version of the tractable class defined by the broken-triangle property for a known variable ordering.