# on_broken_triangles__f4f0ae38.pdf On Broken Triangles Martin C. Cooper Achref El Mouelhi, Cyril Terrioux Bruno Zanuttini IRIT Aix-Marseille University, LSIS GREYC University of Toulouse 3 achref.elmouelhi@lsis.org Normandie University cooper@irit.fr cyril.terrioux@lsis.org bruno.zanuttini@unicaen.fr A binary CSP instance satisfying the brokentriangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP. 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 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 domain D(x) of values for each variable x 2 X, 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 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 domain D(x) of values for each variable x 2 X, a set No Goods(I) consisting of incompatible tuples. 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 No Goods(I). A solution is a partial solution on X. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16) Figure 1: A broken triangle on two values a, b for a given variable x. 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 I0 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 Figure 2: (a) A broken triangle exists on values a0, b0 at variable z. (b) After BTP-merging of values a and b in D(x), this broken triangle has disappeared. 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 I0 the new instance in which a,b have been merged into a new value c. Clearly, if I is satisfiable then so is I0. It suffices to show that if I0 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 I0 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 I0. 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 I0 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 Im 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 Im 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 Im 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 hhhhhh (((((( hhhhhh (((((( Figure 3: (a) This instance contains no broken triangle. (b) After BTP-merging of values a and b in D(x), a broken triangle has appeared on values a0, b0 2 D(z). domain Ninst Nval Ndel Pdel BH-4-13 6 7,334 3,201 44% BH-4-4 10 674 322 48% BH-4-7 20 2,102 883 42% ehi-85 98 2,079 891 43% ehi-90 100 2,205 945 43% gr-col/school 8 4,473 104 2% gr-col/sgb/book 26 1,887 534 28% job Shop 45 6,033 388 6% marc 1 6400 6,240 98% os-taillard-4 30 2,932 1,820 62% os-taillard-5 28 6,383 2,713 43% rlfap Graphs Mod 5 14,189 5,035 35% rlfap Scens 5 12,727 821 6% rlfap Scens Mod 9 9,398 1,927 21% others 1919 1,396 28 0.02% 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 Competition1. 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- 1http://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 No Goods(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 No Goods(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 [ 2. t [ {hx, bi}, u [ {hx, ai} 2 No Goods(I) 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 I0 with the new set of nogoods defined as follows: No Goods(I0) = {t 2 No Goods(I) | hx, ai, hx, bi /2 t} [ {t [ {hx, ci} | t [ {hx, ai} 2 No Goods(I) 9t0 2 No Goods(I) s.t. t0 t [ {hx, bi}} [ {t [ {hx, ci} | t [ {hx, bi} 2 No Goods(I) 9t0 2 No Goods(I) s.t. t0 t [ {hx, ai}} 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 I0 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