b

DiscoverSearch
About
A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms
2020·arXiv
Abstract
Abstract

TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et al., 1991], get rid of unary constraints by binarizing them after having added an ”origin of the world” variable. The constraints become therefore exclusively binary; additionally, a TCSP verifies the property that it is nodeconsistent and arc-consistent. Path-consistency, the next higher local consistency, solves the consistency problem of a convex TCSP, referred to in [Dechter et al., 1991] as an STP (Simple Temporal Problem); more than that, the output of path-consistency applied to an n + 1-variable STP is a minimal and strongly n+1-consistent STP. Weaker versions of path-consistency, aimed at avoiding what is referred to in [Schwalb and Dechter, 1997] as the ”fragmentation problem”, are used as fil-tering procedures in recursive backtracking algorithms for the consistency problem of a general TCSP. In this work, we look at the constraints between the ”origin of the world” variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth’s [1977] well-known arc-consistency algorithm AC-3. We show that if an STP is bdArc-Consistent, and its ”origin of the world” variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures: one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose ”origin of the world” variable is disconnected from none of the other variables; the other for the task of getting a solution from a bdArc-Consistent STP whose ”origin of the world” variable is disconnected from none of the other variables. We then show how to use our results both in a general TCSP solver and in a TCSP-

based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth’s [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.

Constraint-based temporal reasoning, or CTR, came as a generalisation of discrete constraint satisfaction problems, or discrete CSPs [Montanari, 1974; Mackworth, 1977; Freuder, 1982], to continuous variables. Qualitative approaches to CTR include Allen’s [1983] highly influential Interval Algebra, and quantitative approaches to it include the equally influential framework of Temporal Constraint Satisfaction Problems, or TCSPs [Dechter et al., 1991]. Main research issues dealt with in CTR include:

1. the extraction of tractable subclasses, for which polynomial algorithms, incomplete for the general, subsuming language, become complete [Bessi`ere, 1996; Bessi`ere et al., 1996; Broxvall et al., 2002; Isli, 2001; Ligozat, 1996; Nebel and B¨urckert, 1995; van Beek, 1992]; and

2. the design of general algorithms, with an exponential worst-case computational complexity, but with a nice computational behaviour on known classes of real-life problems [Ladkin and Maddux, 1994; Ladkin and Reinefeld, 1992;

Nebel, 1997; Schwalb and Dechter, 1997; Stergiou and Koubarakis, 2000; van Beek, 1992; van Beek and Manchak, 1996].

The constraints of a Temporal Constraint Satisfaction Problem (TCSP) [Dechter et al., 1991] were first defined as being either unary or binary. Then, in the same article, the definition has been modified through the addition of a new variable referred to as the ”origin of the world” variable, which is used to binarize the unary constraints. This addition of an ”origin of the world” variable makes the constraints of a TCSP exclusively binary, with the consequence that a TCSP verifies then the properties of node- and arc-consistencies.

While the adding of an ”origin of the world” variable has the advantage of transforming the solving of an STP, i.e., a TCSP whose constraints are convex, into a shortest paths problem, it remains that, because a TCSP becomes then nodeand arc-consistent, it gets easy for one’s attention to immediately skip to the next higher local consistency, path-consistency, which is exactly what seems to have happened in [Dechter et al., 1991].

In this work, while we will keep the idea of having an ”origin of the world” variable, and of binarizing the unary constraints, making the constraints of a TCSP exclusively binary, we will look at the constraints between the ”origin of the world” variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we de-fine a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArcConsistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth’s [1977] well-known arc-consistency algorithm AC-3. We show that if an STP is bdArc-Consistent, and its ”origin of the world” variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures:

1. one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose ”origin of the world” variable is disconnected from none of the other variables;

2. the other for the task of getting a solution from a bdArcConsistent STP whose ”origin of the world” variable is disconnected from none of the other variables.

We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth’s [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.

The rest of the paper is organized as follows. Section 2 is devoted to needed background. Section 3 defines our notion of binarized-domains Arc-Consistency (bdArc-Consistency) for TCSPs; provides, and studies the termination and the computational complexity of, our algorithm bdAC-3 achieving bdArc-Consistency for a general TCSP; shows the minimality result alluded to above; and ends with an important corollary providing a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Sections 4 and 5 provide the two backtrack-free procedures referred to above. Section 6 provides a general TCSP solver using a weak version of bdArc-Consistency (wbdArc-Consistency) as the fil-tering procedure during the search, whose correctness is a direct consequence of our minimality result of Section 3. A TCSP-based job shop scheduler, which is an adaptation of the general TCSP solver but uses nevertheless bdAC-3 as the filtering procedure instead of a weak version of it, is described in Section 7. Section 8 is devoted to a discussion of the most related literature, and, in particular, provides an adaptation to TCSPs of the other three local consistency algorithms in [Mackworth, 1977]: the arc-consistency algorithm AC-1, and the path-consistency algorithms PC-1 and PC-2; it also corrects an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997]. Section 9 summarizes the work and provides some of its possible future directions.

Temporal Constraint Satisfaction Problems, or TCSPs for short, have been proposed in [Dechter et al., 1991] as an extension of (discrete) CSPs [Mackworth, 1977; Montanari, 1974] to continuous variables.

Definition 1 (TCSP [Dechter et al., 1991]). A TCSP is a pair P = (X, C) consisting of (1) a finite set X of n variables, X1, . . . , Xn, ranging over the universe of time points; and (2) a finite set C of Dechter, Meiri and Pearl’s constraints (henceforth DMP constraints) on the variables.

A DMP constraint is either unary or binary. A unary constraint has the form  Xi ∈ Ci, and a binary constraint the form (Xj − Xi) ∈ Cij, where  Ciand  Cijare subsets of the set IR of real numbers, and  Xiand  Xjare variables ranging over the set IR seen as the universe of time points. A unary constraint Xi ∈ Cimay be seen as a special binary constraint if we consider an origin of the World (time 0), represented by a variable  X0: Xi ∈ Ciis then equivalent to  (Xi −X0) ∈ C0i,with C0i = Ci. Unless explicitly stated otherwise, we assume, in the rest of the paper, that the constraints of a TCSP are all binary. Furthermore, without loss of generality, we make the assumption that all constraints  (Xj − Xi) ∈ Cijof a TCSP are such that i < j: if this is not the case for a constraint (Xj −Xi) ∈ Cij, we replace it with the equivalent constraint (Xi − Xj) ∈ C⌣ij, where  C⌣ijis the converse of  Cij(see the definition of converse below).

Definition 2 (STP [Dechter et al., 1991]). An STP (Simple Temporal Problem) is a TCSP of which all the constraints are convex, i.e., of the form  (Xj − Xi) ∈ Cij, Cijbeing a convex subset of IR.

A universal constraint for TCSPs in general, and for STPs in particular, is of the form  (Xj −Xi) ∈ IR, and is equivalent to “no knowledge” on the difference  (Xj − Xi). An equality constraint is of the form  (Xj − Xi) ∈ {0}: it “forces” variables  Xiand  Xjto be equal.

We now consider an n + 1-variable TCSP P = (X, C), with  X = {X0, X1, . . . , Xn}, the variable  X0representing the origin of the World. Without loss of generality, we assume that P has at most one constraint per pair of variables.

Definition 3 (network representation). The network representathon of P is the labelled directed graph of which the vertices are the variables of P, and the edges are the pairs (Xi, Xj)of variables on which a constraint  (Xj −Xi) ∈ Cijis specified. The label of edge  (Xi, Xj)is the set  Cijsuch that (Xj − Xi) ∈ Cijis the constraint of P on the pair  (Xi, Xj)of variables.

Definition 4 (matrix representation). The matrix representation of P is the  (n + 1) × (n + 1)-matrix, denoted by P for simplicity, defined as follows:  Pii = {0}, ∀i = 0 . . . n; Pij = Cijand  Pji = {as.t.  (−a) ∈ Cij}, for all  i ̸= jsuch

that a constraint  (Xj −Xi) ∈ Cijis spectfied on  Xiand  Xj; Pij = IR, for all other pairs (i, j). Definition 5 ((consistent) instantiation). An instantiation of P is any n+1-tuple  (x0, x1, . . . , xn) ∈ IRn+1, representing an assignment of a value to each variable. A consistent instantiation, or solution, is an instantiation satisfying all the constraints: for all  i, j, (Xi = xi, Xj = xj)satisfies the constraint, if any, specified on the pair  (Xi, Xj). Definition 6 (subnetwork). A k-variable subnetwork,  k ≤n + 1, is any restriction of the network P to k of its variables and the constraints on pairs of those k variables. Definition 7 ((strong) k-consistency). For all k = 1 . . . (n + 1), P is k-consistent if any solution to any  (k − 1)-variable subnetwork extends to any k-th variable; it is strongly k-consistent if it is j-consistent, for all  j ≤ k.

Strong 1-, 2- and 3-consistencies correspond to node-, arc- and path-consistencies, respectively [Montanari, 1974; Mackworth, 1977]. Strong (n + 1)-consistency of P corresponds to decomposability [Dechter, 1992]. It facilitates the exhibition of a solution by backtrack-free search [Freuder, 1982].

The consistency problem of a TCSP, i.e. the problem of verifying whether it has a consistent instantiation, is NP-hard. Davis [1989] (cited in [Dechter et al., 1991]) showed that even the subclass of TCSPs in which the constraints are of length lower than or equal to 2 (i.e. they are of the form  (Xj−Xi) ∈ Cij, with  Cijbeing a convex set or a union of two disjoint convex sets) is NP-hard (see also [Dechter et al., 1991], Theorem 4.1, Page 73). However, when the constraints of a TCSP are all convex, i.e. when we restrict ourselves to STPs, the consistency problem is polynomial [Dechter et al., 1991]. Moreover, in the case of STPs the classical path-consistency method [Montanari, 1974; Mackworth, 1977] leads to strong (n + 1)-consisteny [Dechter et al., 1991]. Definition 8 (converse). The converse of a DMP constraint (Xj − Xi) ∈ Cijis the DMP constraint  (Xi − Xj) ∈ C⌣ijsuch that  C⌣ij = {−asuch that  a ∈ Cij}: (Xj − Xi) ∈Cij ⇔ (Xi − Xj) ∈ C⌣ij. Definition 9 (intersection). The intersection of two DMP constraints  (Xj − Xi) ∈ C1ijand  (Xj − Xi) ∈ C2ij, on the same pair of variables, is the DMP constraint  (Xj − Xi) ∈Cij, with  Cij = C1ij ∩ C2ij. Definition 10 (composition). The composition of two DMP constraints  (Xk − Xi) ∈ Cikand  (Xj − Xk) ∈ Ckj, written (Xk − Xi) ∈ Cik ⊗ (Xj − Xk) ∈ Ckj, is the constraint (Xj −Xi) ∈ Cikj, on the extreme variables  Xiand  Xj, such that  Cikj = {c : ∃a ∈ Cik, ∃b ∈ Ckjs.t. c = a + b}. We will also say that the composition of the sets  Cikand  Ckjis the set  Cikj: Cik ⊗ Ckj = Cikj. Definition 11 (Minimal partition into convex subsets). Let S be a subet of  IR: S ⊆ IR. The minimal partition of S into convex subsets, or mPcs(S) for short, is the set mPcs(S) = {S1, . . . , Sp}such that  S1 ∪ . . . ∪ Spis a partition of S into maximal convex subsets: for all  i ∈ {1, . . ., p}: (1)  Siis convex, and (2) for all convex set  S′, if  Si ⊂ S′then  S′is not a subset of S.

Applying PC even to a TCSP whose constraints are initially of length lower than or equal to 2, may lead to the so-called “fragmentation problem” [Schwalb and Dechter, 1997]: the constraints may be “fragmented”. Schwalb and Dechter [1997] gave a number of weak versions of PC, which are less effective but have the advantage of getting rid of the fragmentation problem. One of these versions is ULT (UpperLower Tightening), which we will also refer to as weak Path-Consistency, or wPC for short. It consists of PathConsistency (PC) in which the usual composition operation is replaced by weak composision. Definition 12 (Convex closure). The convex closure of a set  A ⊆ IR, cc(A), is the smallest convex set verifying A ⊆ cc(A). The convex closure of a TCSP constraint (Xj−Xi) ∈ Cijis the TCSP constraint  (Xj−Xi) ∈ cc(Cij). The convex closure of a TCSP P, cc(P), is the STP cc(P) = (X, C′), with  C′ = {(Xj − Xi) ∈ cc(Cij) : (Xj − Xi) ∈Cijconstraint of P}. Definition 13 (weak composition [Schwalb and Dechter, 1997]). The weak composition of two DMP constraints  (Xk − Xi) ∈ Cikand  (Xj − Xk) ∈ Ckj, written  (Xk − Xi) ∈ Cik ⊗w (Xj − Xk) ∈ Ckj, is the composition of their convex closures; i.e., (Xk − Xi) ∈ Cik ⊗w (Xj − Xk) ∈ Ckjis equal to (Xk − Xi) ∈ cc(Cik) ⊗ (Xj − Xk) ∈ cc(Ckj).

image

tively,  Cij := Cij ∩ Cik ⊗w Ckj) as the path-consistency operation (respectively, the weak path-consistency operation) on triangle  (Xi, Xk, Xj). Applying path consistency (respectively, weak path-consistency) to a TCSP consists of repeating, until stability is reached or inconsistency is detected, the process of applying the path-consistency operation (respectively, the weak path-consistency operation) to each triangle (Xi, Xk, Xj)of variables. We will also refer to the (weak) path-consistency operation as a relaxation step. Example 1 illustrates some of the introduced notions, including the fragmentation problem. Example 1. Let P = (X, C) be a TCSP, with X =

image

[10, 15]}, and the network representation given by Figure 1:

image

image

Figure 1: The network representation of the TCSP of Example 1.

4. If, instead of the path-consistency operation, we used the weak path-consistency operation, we would get  C02 =[−6, −1] ∪ [1, 20], which does not fragment the label on edge  (X0, X2).

Remark 1. Let  (Xi, Xk, Xj)be a triangle subnetwork of a TCSP P, with |mPcs(Cij)| = n1, |mPcs(Cik)| = n2and |mPcs(Ckj)| = n3: 1. the worst-case computational complexity of the path-consistency operation,  Cikj = Cij ∩ Cik ⊗ Ckj, on triangle  (Xi, Xk, Xj)is  O(n1 + n2n3) = O(n2n3); 2. the worst-case computational complexity of the weak path-consistency operation,  Cikj = Cij ∩ Cik ⊗w Ckj, on triangle  (Xi, Xk, Xj)is  O(n1); and 3. if  Cij, Cikand  Ckjare convex, the worst-case computational complexity of both operations is O(1). See Appendix A for details.

A distance graph is a complete labelled (weighted) directed graph G = (V, E, w), where V is the set of vertices (nodes),  E = V × Vis the set of edges, and w is a labelling (weight) function from E to the set  IR ∪ {+∞}verifying w(Vi, Vi) = 0, for all vertices  Vi. A rooted distance graph is a pair (G, S), where G is a distance graph and S is a vertex of G. A path of length p, or p-path, of a distance graph is a sequence  π = (Vi0, · · · , Vip)of vertices. The length of a path gives the number of its edges. Let  π = (Vi0, · · · , Vip)be a p-path of a distance graph G = (V, E, w). πis elementary if, for all j, k such that {j, k} ̸= {0, p}, if  j ̸= kthen  Vij ̸= Vik; it is a circuit if  Vi0 = Vip. The weight function w of G can be extended to paths as follows. The weight of  πis the sum w(π) = �p−1j=0 w(Vij , Vij+1). A (strictly) negative circuit is a circuit whose weight is strictly negative. We now define the distance graph and the rooted distance graph of an STP. Definition 14 ((rooted) distance graph of an STP). If the TCSP P = (X, C) is an STP, its distance graph is the distance graph  G = (X, X × X, w)constructed as follows: 1. the set of vertices of G is the set X of variables of P 2. The labelling function w is built as follows: (a) for all variables  Xiand  Xj, with i < j, if P has a constraint  (Xj − Xi) ∈ Cij, with  Cijof the form  (−∞, b], [a, b]or (a, b], then the label of edge (Xi, Xj)is  b: w(Xi, Xj) = b(b) for all variables  Xiand  Xj, with i < j, if P has a constraint  (Xj − Xi) ∈ Cij, with  Cijof the

form  (−∞, b), [a, b)or (a, b), then the label of edge (Xi, Xj)is  b−: w(Xi, Xj) = b−

(c) for all variables  Xiand  Xj, with i < j, if P has a constraint  (Xj − Xi) ∈ Cij, with  Cijof the form  [a, +∞), [a, b]or [a, b), then the label of edge (Xj, Xi)is  −a: w(Xj, Xi) = −a

(d) for all variables  Xiand  Xj, with i < j, if P has a constraint  (Xj − Xi) ∈ Cij, with  Cijof the form  (a, +∞), (a, b]or (a, b), then the label of edge (Xj, Xi)is  (−a)−: w(Xj, Xi) = (−a)−

image

We refer to the rooted distance graph  (G, X0)as the rooted distance graph of the STP P.

image

Theorem 1 ([Pratt, 1977; Shostak, 1981]). Let P be an STP. P is consistent if and only if its distance graph has no negative circuit.

The use of labelled directed graphs to represent a conjunction of linear inequalities, as used in [Dechter et al., 1991], is restricted to large inequalities of the form  Xj − Xi ≤ a, where  a ∈ IR. An idea similar to the one used in this work, which combines large and strict inequalities, can be found in [Kautz and Ladkin, 1991]. Definition 15 (d-graph of an STP). The d-graph of an STP P = (X, C) is the distance graph  G = (X, X × X, w)verifying:  w(Xi, Xj)is the weight of the shortest path from  Xito  Xjin the distance graph of P.

The d-graph of an STP can be built from its distance gragh using Floyd-Warshall’s all-to-all shortest paths algo- rithm [Aho et al., 1976; Papadimitriou and Steiglitz, 1982].

image

Figure 2: The table M for the transformation of a rooted distance graph to an STP, with  a, b ∈ IR.

Definition 16 (STP of a rooted distance graph). Let  (G, V0)be a rooted distance graph, with  G = (V, V × V, w)and V = {V0, V1, . . . , Vn}. The STP of  (G, V0)is the STP P = (X, C), with  X = {X0, X1, . . . , Xn}, constructed as follows:

1. Initialise C to the empty set:  C = ∅;

2. for all vertices  Viand  Vjof G, with i < j, such that at least one of the two edges  (Vi, Vj)and  (Vj, Vi)is not labelled with  +∞:

image

(b) add to C the constraint  (Xj − Xi) ∈ M[l1, l2], where  M[l1, l2]is as given by the table M of Figure 2 (l1of the form  +∞, aor  a−, with  a ∈ IR; and  l2of the form  +∞, bor  b−, with  b ∈ IR).

For instance, if the edges  (V1, V5)and  (V5, V1)are labelled, respectively, with 6 and  (−2)−, the constraint  (X5 − X1) ∈(2, 6] is added to C.

In [Dechter et al., 1991], it has been shown that applying path-consistency to an STP P is equivalent to applying Floyd-Warshall’s all-to-all shortest paths algorithm [Aho et al., 1976; Papadimitriou and Steiglitz, 1982] to the distance graph of P. In other words, if  P ′is the STP resulting from applying path consistency to  P (P ′ = PC(P)), then  P ′is exactly the STP of the d-graph of P. Furthermore, P ′is minimal and strongly n + 1-consistent, n + 1 being the number of variables.

Theorem 2 ([Dechter et al., 1991]). Let P be an n + 1-variable STP. If path-consistency applied to P does not detect an inconsistency, then the resulting STP  P ′is minimal and strongly n + 1-consistent. Furthermore,  P ′is the STP of the d-graph of P.

For the detection of an STP’s inconsistency, which is equivalent to the detection of a negative circuit in its distance graph [Pratt, 1977; Shostak, 1981], we will need a lower bound of the weight of a finite-weight elementary path. Furthermore, for the purpose of evaluating the computational behaviour of the binarized-domains Arc-Consistency algorithm to be de-fined, we will additionaly need a upper bound of the same weight. These are defined as follows.

Definition 17 (path-lb, path-ub of an STP). Let P = (X, C) be an n+1-variable STP,  G = (X, X ×X, w)its rooted distance graph, and  Edges<(P)and  Edges≥(P)the following subsets of  X × X:

Edges<(P) = {(Xi, Xj) : i ̸=j and w(Xi, Xj)< 0 and w(Xi, Xj)< w(Xj, Xi)} ∪ {(Xi, Xj) :i < j and w(Xi, Xj) < 0and w(Xi, Xj) = w(Xj, Xi)},

image

Definition 18 (path-lb, path-ub of a TCSP). Let P = (X, C) be an n + 1-variable TCSP: path-lb(P) = path-lb(cc(P)) and path-ub(P) = path-ub(cc(P)). Theorem 3. Let P = (X, C) be an n+1-variable STP, G = (X, X × X, w)its distance graph, and  u = (Xi1, . . . , Xip)an elementary path of G that is not a circuit. If the weight w(u) of u is finite then path-lb(P) ≤ w(u) ≤path-ub(P). Proof : Let u be an elementary path of G, of finite weight: 1. The lowest weight possible for u, when  |Edges<(P)| ≤n, correponds to the case when the edges of u are exactly those in  Edges<(P); and when  |Edges<(P)| > n, it corresponds to the case when the edges of u are the first n in  Edges<(P). In both cases, the weight is equal to path-lb(P). 2. The uppest weight possible for u, when  |Edges≥(P)| ≤n, correponds to the case when the edges of u are exactly those in  Edges≥(P); and when  |Edges≥(P)| > n, it corresponds to the case when the edges of u are the first n in  Edges≥(P). In both cases, the weight is equal to path-ub(P).

The transformation of the unary constraints of a TCSP into binary constraints, after the addition of an ”origin of the world” variable  X0, makes the constraints of the TCSP become exclusively binary. In this work, we look at the constraints between the ”origin of the world” variable  X0and the other variables as representing the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains arc-consistency, or bdAC for short.

Definition 19 (binarized-domains arc-consistency). Let P be a TCSP. P is said to verify the binarized-domains arc-consistency, or to be bdArc-Consistent for short, if for all all  i, j ∈ {1, . . . , n}, i ̸= j, the following holds:  P0i ⊆P0j ⊗ Pji. Said differently, P is bdArc-Consistent if, for all  i, j ∈{1, . . . , n}, i ̸= j, the following holds: for all  (a0, ai) ∈ IR2such that  (ai − a0) ∈ P0i, there exists  aj ∈ IRsuch that (aj − a0) ∈ P0jand the instantiation  (Xi, Xj) = (ai, aj)satisfies the constraints, if any, on variables  Xiand  Xj. Definition 20. Let P be a TCSP, and  Xiand  Xjtwo variables of  P. Xjis reachable from  Xiif and only if there exists a finite-weight elementary path from  Xito  Xjin the distance graph of cc(P), the convex closure of  P. Xjis disconnected from  Xiif none of  Xiand  Xjis reachable from the other; Xjis connected to  Xiotherwise. P is connectd if  X0is connected to each of the other variables. The algorithm of Figure 4 takes as input a TCSP P, and does the following: 1. it makes P bd-ArcConsistent, if at all possible, 2. if P cannot be made bd-ArcConsistent then it is inconsistent, and the algorithm detects the inconsistency. We refer to the algorithm as bdAC-3, for it is mainly an adaptation of Mackworth’s [1977] well-known arc-consistency algorithm AC-3. bdAC-3 initialises a queue Q to all pairs (i, j) such that  i ̸= 0, j ̸= 0, i ̸= jand P contains a (binary) constraint on  Xiand  Xj. Then it proceeds by taking in turn the pairs in Q for propagation. When a pair (k, m) is taken (and removed) from Q, bdAC-3 calls the procedure REVISE (Figure 3) which eventually updates  P0k, which represents the binarized domain of  Xk, if it is not a subset of the composition  P0m ⊗ Pmk. The main difference of bdAC-3 with Mackworth’s [1977] AC-3 lies in line 4 of procedure REVISE, which guarantees termination of bdAC-3, and can be explained as follows, where the notations lowerB(A) and upperB(A), for a set  A ⊆ IR, refer, respectively, to the lower bound and upper bound of A: If P is an STP,  −lowerB(P0k)and  upperB(P0k)stand for the current values of the weights of the shortest paths from  Xkto  X0and from  X0to  Xk, respectively, in the rooted distance graph of P. Those of the two that are finite should satisfy the conditions of Theorem 3. In other words, the algorithm should make sure that the evolution of the two weights makes none of them get below the lower bound path-lb(P). Should the condition get violated, this would correspond to the detection of a negative circuit in the rooted distance graph of P, and bdAC-3 would terminate with a negative answer to the consistency problem of P. If P is a general TCSP, given that path-lb(P) = path-lb(cc(P)) and that P is a refinement of its convex closure cc(P), line 4 of procedure REVISE still applies. If the REVISE procedure successfully updates  P0k, without making it become empty, the pairs (i, k) such that  i /∈{0, k, m} and P has a constraint on  Xiand  Kk, reenter the queue Q if they are no longer there. The algorithm terminates

image

2. temp  = P0i ∩ P0j ⊗ Pji; 3. if(temp  ̸= P0i){

4. if[temp  ̸= ∅and (lowerB(temp) > −path-lb(P)

or upperB(temp) < path-lb(P))]temp  = ∅; 5. P0i =temp;Pi0 =temp⌣;

6. DELETE=true 7. }

8. return DELETE 9. }

Figure 3: The boolean procedure REVISE.

image

1. Q = {(i, j) : P has a constraint on Xiand Xj, i  ∗ j ̸= 0, i  ̸= j};

2. Emptydomain = false; 3. while  (Q ̸= ∅and (not Empty

4. select and delete an arc (k, m) from Q; 5. if REVISE(k, m)

6. if  (P0k = ∅)Emptydomain = true 7. else Q  = Q ∪ {(i, k) : P has a constraint

image

10. }%end bdAC3

Figure 4: The binarized-domains Arc-Consistency algorithm bdAC-3.

when a binarized domain becomes empty, or when the queue Q becomes empty. This leads us to the following Theorem.

Theorem 4. Le P be a TCSP. The bdAC-3 algorithm applied to P terminates and, either detects inconsistency of P or computes a bd-Arc Consistent TCSP equivalent to P.

The range of a TCSP will be needed for the determinination of the computational complexity of bdAC-3:

Definition 21 (range of a TCSP). Let P = (X, C) be an n+1-variable TCSP. The range of P, rg(P), is defined as rg(P) = path-ub(P) −path-lb(P).

Theorem 5. Let P = (X, C) be a TCSP, with |X| = n + 1 and |C| = m. bdAC-3 applied to P can be achieved in O(n2R) = O(mR)relaxation steps (calls of the procedure REVISE of Figure 3) and  O(n2R3) = O(mR3)arithmetic operations, where R = rg(P) is the range of P expressed in the coarsest possible time units.

Proof: The worst case scenario of bdAC-3 occurs when, whenever the procedure REVISE updates  P0i, the length of the set  P0idecreases by one time unit. Furthermore, if  P0ihas a finite bound, it will be in the set [path-lb(P), path-ub(P)] (Theorem 3). Therefore,  P0ican be updated at most path-ub(P) −path-lb(P) = R = O(R) times. The pairs (i, j) that enter initially the queue Q of bdAC-3 are such that there is a constraint of P on  Xiand  Xj. A pair (k, i) can reenter the queue O(R) times, whenever  P0ihas been updated. Because there are  m = O(n2)constraints, the number of relaxation steps is  O(mR) = O(n2R). A relaxation step consists of a call REVISE(i, j) consisting mainly of the computation of a path consistency operation of the form P0i = P0i ∩ P0j ⊗ Pji, which needs  O(R2)arithmetic operations since each of the three sets  P0i, P0jand  Pjiis a union of at most R convex subsets. The whole algorithm therefore terminates in  O(mR3) = O(n2R3)time.

For an STP, a relaxation step is in O(1) (see Remark 1). This justifies the following corollary to Theorem 5.

Corollary 1. Let P = (X, C) be an STP, with |X| = n + 1 and |C| = m. bdAC-3 applied to P can be achieved in O(n2R) = O(mR)relaxation steps (calls of the procedure REVISE of Figure 3) and  O(n2R) = O(mR)arithmetic operations, where R = rg(P) is the range of P expressed in the coarsest possible time units.

Theorem 6. Let P be a connected STP (no variable  Xi, i >0, is disconnected from  X0). If P is bdArc-Consistent, its (binarized) domains are minimal: for all  i ∈ {1, . . ., n}, for all a ∈ P0i, there exists a solution  (X0, X1, . . . , Xi, . . . , Xn) =(t0, t1, . . . , ti, . . . , tn)such that  ti − t0 = a.

image

(G, X0)be the rooted distance graph of P, with G = (X, X × X, w). According to Theorem 2, showing that the binarized domains  P0i, with  i ∈ {1, . . ., n}, are minimal, is equivalent to showing that the labels (weights)  w(X0, Xi)and  w(Xi, X0)are the weights of the shortest paths from  X0to  Xiand from  Xito  X0, respectively. Suppose that this is not the case; in other words, that for some  i ∈ {1, . . . , n}, either  w(X0, Xi)is not the weight of the shortest path from X0to  Xi, or  w(Xi, X0)is not the weight of the shortest path from  Xito  X0:

image

Summing the left-hand sides and the right-hand sides of the linear inequalities, we get: w(Xi0, Xik) +Σk−1l=2 w(Xi0, Xil) ≤ w(Xii0 , Xi1) + w(Xi1, Xi2) +

· · · + w(Xik−1, Xik) + Σk−1l=2 w(Xi0, Xil). This, in turn, gives  w(Xi0, Xik) ≤ w(Xii0 , Xi1) + w(Xi1, Xi2) +· · · + w(Xik−1, Xik), which clearly contredicts our supposition.

2. Case 2: w(Xi, X0)is not the weight of the shortest path from  Xito  X0. This would mean the existence of j in  {1, . . ., n}, j ̸= i, and of a path < Xi0 = Xi, Xi1 = Xj, . . . , Xik = X0 >from  Xito  X0through  Xj, whose weight is strictly smaller than  w(Xi, X0): w(Xi0, Xi1) + w(Xi1, Xi2) + · · · +w(Xik−1, Xik) < w(Xi0, Xik). But, because the STP is bdArc-Consistent, we have the following:

image

Summing the left-hand sides and the right-hand sides of the linear inequalities, we get: w(Xi0, Xik) +Σk−2l=1 w(Xil, Xik) ≤ w(Xi0, Xi1)+w(Xi1, Xi2)+· · ·+w(Xik−1, Xik) + Σk−2l=1 w(Xil, Xik). This, in turn, gives w(Xi0, Xik) ≤ w(Xi0, Xi1) + w(Xi1, Xi2) + · · · +w(Xik−1, Xik), which clearly contredicts our supposition.

As an immediate consequence of Theorem 6:

Corollary 2. Let (G, V ) be a rooted distance graph. The bdArc-Consistency algorithm bdAC-3 can be used to compute the weights of the shortest paths from V to all vertices of G, and the weights of the shortest paths from all vertices of G to V .

Proof. Proceed as follows:

1. Linearly transform the input rooted distance graph (G, V ) into its STP P;

2. apply the bdArc-Consistency algorithm bdAC-3 to P;

3. linearly transform the STP resulting from bdAC-3 into its rooted distance graph.

Appendices B and C present two detailled examples. The example of Appendix B applies the bdAC-3 algorithm to an STP, transforming the latter into a bdArc-Consistent STP with no variable disconnected from the ”origin of the world” variable, without making a binarized domain become empty. The example of Appendix C applies bdAC-3 to an STP whose rooted distance graph presents a negative circuit not reachable from  X0, the ”origin of the world” variable, but from which X0is reachable: bdAC-3 detects the negative circuit, and the inconsistency of the STP. In particular, the example of Appendix C shows that bdAC-3 without line 4 of procedure REVISE, which could be seen as a ”literal” adaptation to TCSPs of Mackworth’s [1977] algorithm AC-3, has no guarantee to always terminate (see Remark 3).

Remark 3. We refer to the procedure REVISE of Figure 3 without its line 4 as REVISE−, and to the algorithm bdAC-3 (Figure 4) in which procedure REVISE is replaced with REVISE−as bdAC-3−. bdAC-3−is, somehow, a ”literal”

Input: The matrix representation of a bdArc-Consistent STP P having variables disconnected from  X0.

Output: Extracts a connected bdArc-Consistent STP re-finement of P, and returns true, if P consistent; returns false otherwise.

image

1. select a variable  Xidisconnected from  X0, and a real number a;

2. P0i = [a, +∞); Pi0 = (−∞, −a]; 3. if(bdAC-3(P))

4. if (P has no variable disconnected from  X0)

image

Figure 5: The polynomial backtrack-free procedure

image

adaptation of Mackworth’s [1977] AC-3 algorithm to TCSPs. In the light of the example of Appendix C, bdAC-3−is not guaranteed to always terminate.

image

Given a bdArc-Consistent STP P, the backtrack-free procedure connectX0inbdACstp(P) of Figure 5 checks consistency of P: it extracts a connected bdArc-Consistent STP refinement of P, and returns true, if P consistent; it returns false otherwise. Correctness of procedure

image

Theorem 7. Let P = (X, C) be a bdArc-Consistent STP with a variable  Xi, i ≥ 1, disconnected from  X0, and  P ′ =(X, C ∪ {(Xi − X0) ∈ [a, +∞)})the STP obtained from P by adding the constraint  (Xi − X0) ∈ [a, +∞), with  a ∈ IR. P is consistent if and only if  P ′is consistent.

Proof: Immediate consequence of Theorem 1 and the fact that the rooted distance graphs of P and  P ′are such that one has a negative circuit if and only if the other has.

image

Correctness of the backtrack-free procedure of Figure 6 is a direct consequence of Theorem 6. If the input bdArcConsistent STP P is not a singleton STP (line 1), we select a non-singleton edge  (X0, Xi)and instantiate it with an element  aiof  P0i(lines 2 and 3): because P is connected and bdArc-Consistent, the binarized domain  P0iis minimal (Theorem 6), which guarantees that the element  aichosen to instantiate edge  (X0, Xi)participates in a global solution.

Input: The matrix representation of a bdArc-Consistent STP P with no variable disconnected from  X0.

Output: A bdArc-Consistent singleton-domains STP refinement of P.

image

2. select a non-singleton edge  (X0, Xi);

3. Instantiate  (X0, Xi)with an element  aiof  P0i: P0i = {ai}; Pi0 = {−ai};

4. P = bdAC-3(P); 5. backtrackfree(P)}%endif

6. else return P 7. }

Figure 6: A polynomial backtrack-free procedure computing a consistent singleton refinement of a connected bdArc-Consistent STP.

bdArc-Consistency is then applied to the refinement resulting from the instantiation (line 4). The process needs to be reiterated at most n times before the binarized domains  P0i, i ∈ {1, . . . , n}, become singleton (line 6).

We define a refinement of a TCSP P to be any TCSP  P ′on the same set of variables such that for all constraint  (Xj −Xi) ∈ P′ijof  P ′, the corresponding constraint  (Xj − Xi) ∈Pijof P verifies  P′ij ⊆ Pij. A constraint  (Xj − Xi) ∈ P′ijsuch that  P′ij ⊆ Pijis called sublabel of  (Xj − Xi) ∈ Pij. A refinement is convex if it is an STP [Dechter et al., 1991]. The solver can now be described as follows (see Figure 7). As the filtering procedure during the search, it uses a weak version of the bdArc-Consistency algorithm bdAC-3, which we refer to as wbdAC-3, and consists of replacing composition by weak composition in the REVISE procedure of Figure 3, the aim being to avoid the “fragmentation problem” [Schwalb and Dechter, 1997]. If P is the input TCSP, the recursive procedure consistent(P) is called, which works as follows. The filtering procedure wbdAC-3 is applied (the very first application of the filtering, at the root of the search space, consists of the preprocessing step). If the wbdAC-3 fil-tering detects an inconsisteny (line 1), by reducing a binarized domain to the empty set, a failure (dead end) is reached and the procedure returns false. Otherwise, if P has no disjunctive edge (line 10) then the result of the wbdAC-3 filtering is a bdArc-Consistent STP, which is not necessarily consistent since it might contain a negative circuit disconnected from X0; and, in this case, the procedure does the following:

1. if P has no variable disconnected from  X0then P is consistent (Theorem 6), and the procedure returns true (line 11);

2. if P has variables that are disconnected from  X0(line

image

2. else 3. if(P has disjunctive edges){%beginif2

4. select a disjunctive edge  (Xi, Xj);

5. let mPcs(Pij) = {Pij1, . . . , Pijnij };

6. for(k = 1 to  nij){7. P ′ = P; P ′ij = Pijk; P ′ji = P ⌣ijk;

8. if(consistent(P ′))return true}%endfor 9. return false}%endif2

10. else 11. if (P has no variable disconnected from  X0)

image

12. else return connectX0

inbdACstp(P) 13. }

Figure 7: The recursive procedure consistent(P).

12), these might hide a negative circuit, of which  X0cannot be a vertex. The backtrack-free search procedure connectX0inbdACstp(P) is called, which checks consistency of P: consistent(P) returns the result returned by connectX0inbdACstp(P). If the result of the wbdAC-3 filtering is not an STP then there remain disjunctive edges (line 3). A disjunctive edge is selected (lines 4 and 5) and instantiated with one of its maximal convex sublabels (line 7):  P ′is the refinement of P resulting from the instantiation. The recursive call  consistent(P ′)is then made (line 8). If  consistent(P ′)returns true, consistent(P) returns true. If now  consistent(P ′)returns false, the next maximal convex sublabel, if any, of the edge being instantiated is chosen, and the recursive call consistent(P ′)is made again. If all sublabels have been already chosen (line 9) then consistent(P) returns false. Completeness of the solver is guaranteed by completeness of bdArc-Consistency for connected STPs (Theorem 6). Given an input TCSP P, the solver of Figure 7 can be adapted so that, when P is consistent, it returns a connected bdArc-Consistent STP refinement  P ′of P. From  P ′, one can then get a solution to P with the use of the polynomial backtrack-free procedure of Figure 6. The next section describes how, from the general TCSP solver, one can extract a TCSP-based job shop scheduler with bdAC-3 as the filtering procedure during the search.

Many approaches to scheduling are known in the literature, among which mathematical programming, timed Petri nets [Carlier et al., 1985] and discrete CSPs [Dincbas et al., 1990; Sadeh et al., 1995]. We focus on job shop scheduling problems.

Input: The matrix representation of a scheduling TCSP P. Output: The optimum z of P.

Method: Initialise the optimum:  z = +∞; then call the recursive procedure optimum(P) procedure optimum(P){

1. if (not bdAC-3(P) or  z ≤ OLB(P))return

2. else 3. if(P has disjunctive edges){%beginif2

4. select a disjunctive edge  (Xi, Xj); 5. let  A = Pij = A1 ∪ A2;

6. for(k = 1 to 2){ 7. P ′ = P; Pij = Ak; Pji = A⌣k;

8. optimum(P ′)}%endfor 9. }%endif2

image

Figure 8: The TCSP-based job-shop scheduler.

A scheduling TCSP is a TCSP P = (X, C), with X = {X0, X1, . . . , Xn}, X0being the ”origin of the world” variable standing for a global release date, n being the number of (non-preemptive) tasks:

image

(b) the duration of task i is  di, with  di > 0(the tasks are durative, in the sense that their durations are not null; furthermore, they have fixed durations, known in advance); and

(c) the release and due dates of task i, if any, are  rdiand  ddi.

2. A conjunctive (or precedence) constraint between tasks i and j has the form  (Xj − Xi) ∈ [di, +∞).

3. A disjunctive constraint between tasks i and j has the form  (Xj − Xi) ∈ (−∞, −dj] ∪ [di, +∞).

4. A release (respectively, due) date constraint has the form (Xi − X0) ∈ [rdi, +∞)(respectively,  (Xi − X0) ∈[0, ddi − di]).

5. Finally,  X0standing for a global release date, we add the n constraints  (Xi − X0) ∈ [0, +∞), i ∈ {1, . . . , n}.

We define the duration dur(s) of a solution  s = (X0 =t0, X1 = t1, . . . , Xn = tn)of P as  dur(s) = maxni=1(ti +di) − t0; the latency lat(s) of s as the amount of time separating stimulus and response, the stimulus being given at time t0, and the response obtained at the effective beginning of the very first task:  lat(s) = minni=1ti − t0. The optimum of P, tPopt, is defined as  tPopt = mins∈sol(P )dur(s), with sol(P) being the set of solutions of P. The scheduler we propose (Figure 8), with bdAC-3 as the filtering procedure during the search, minimises the makespan and initialises the optimum z to  +∞; it is an adaptation of the TCSP solver of Figure 7. The lower bound of the optimum of P, OLB(P), is defined as OLB(P) = maxni=1(ai+di), where  aiis the lower bound of the binarized domain  P0i. Note that  tPopt ≤ OLB(P), which is used by the scheduler to backtrack whenever  z ≤ OLB(P)(line 1). Furthermore, whenever the bdAC-3 filtering leads to a (bdArc-Consistent) STP (line 10), the optimum is updated in a way one can justify as follows. Given the nature of a scheduling TCSP (X0is a global release date),  X0is disconnected from none of the other variables. Because the binarized domains  P0iof a connected bdArc-Consistent STP P are minimal (Theorem 6), a direct consequence of results in [Dechter et al., 1991] (Corollaries 3.2 and 3.4, Pages 69 and 70) is that the solution realising the optimum of P is given by the lower bounds of these binarized domains, and the optimum itself is OLB(P). See Figure 8 for details.

The relaxation step of the bdAC-3 algorithm, consisting of a call of the REVISE(i, j) procedure of Figure 3, and reducing mainly to the path-consistency operation  P0i =P0i ∩ P0j ⊗ Pji, may result in a fragmentation of the binarized domain  P0i, as illustrated by Example 1. To avoid such a fragmentation, we used in the general TCSP solver of Section 6, a weak version of the bdAC-3 algorithm, wbdAC-3, as the filtering procedure.

The restriction to scheduling TCSPs, however, makes it possible to use bdAC-3 as the filtering procedure, with no risk of fragmenting a binarized domain. Given such a TCSP P = (X, C), with  X = {X0, X1, . . . , Xn}, the binarized domains  P0i, with  i ∈ {1, . . . , n}, are of either of the two forms [a, b] (form A1) or  [a, +∞)(form A2), with  0 ≤ a ≤ b. Furthermore, the entries  Pijof the matrix representation of P, with  i∗j ̸= 0and such that there is a constraint on tasks i and j, are of either of the three forms  (−∞, a]with a < 0 (form B1),  [a, +∞)with a > 0 (form B2), or  (−∞, a] ∪ [b, +∞)with a < 0 < b (form B3). Therefore, the composition P0j ⊗ Pjiof the REVISE(i, j) procedure of Figure 3 results in a convex set with no open finite bound; this implies that, the relaxation operation  P0i = P0i ∩ P0j ⊗ Pjiof the same procedure, replacing the binarized domain  P0iwith its intersection with the composition  P0j ⊗ Pji, results in a binarized domain of either of the two forms A1 or A2. This leads to the following theorem:

Theorem 8. The class of scheduling TCSPs is closed under bdArc-Consistency: applying a bdArc-Consistency algorithm, such as bdAC-3, to a schedulig TCSP P either detects inconsistency of P, or computes an (equivalent, bdArc-Consistent) scheduling TCSP.

Theorem 8 justifies our use of bdAC-3 as the filtering procedure of our TCSP-based scheduler, instead of its weak version wbdAC-3: bdAC-3 applied to a scheduling TCSP does not fragment the binarized domains. Furthermore, given that the instantiation of a disjunctive edge transforms a constraint of the form B3 into a constraint of either of the two forms B1 and B2, the resulting refinement is a scheduling TCSP. This brings us to this nice behavior of the class of scheduling TCSPs: at each node of the scheduler’s search tree, the bdAC-3 filtering either detects inconsistency of the corresponding refinement, indicating a failure (deadend), or computes an (equivalent, bdArc-Consistent) scheduling TCSP.

Related work on arc-consistency for TCSPs include [Cervoni et al., 1994; Cesta and Oddi, 1996; Kong et al., 2018; Planken et al., 2008], but the focus has always been restricted to STPs. The most related remains [Kong et al., 2018], which defines an arc-consistency algorithm for STPs, which can be seen as an adaptation of Bellman-Ford-Moore one-to-all shortest paths algorithm [Bellman, 1958; Ford and Fulkerson, 1962; Moore, 1959]; this can also be seen as an adaptation of Mackworth’s [1977] arc-consistency algorithm AC-1 restricted to one pass. Beyond the fact that the algorithm is defined only for STPs, the other criticism is that for applications needing incrementality such as planning, which seems to have been the authors’ targetted application, it is clear that the use of an adaptation of Mackworth’s [1977] AC-3 instead of AC-1, in case of arc-consistency, and an adaptation of Mackworth’s [1977] PC-2 instead of PC-1, in case of path-consistency, is much better, mainly because these use a queue allowing them, when new knowledge comes in, to continue on what had been done before, and not to redo it. Allen’s well-known Interval Algebra [Allen, 1983] in general, and its convex part in particular, whose most targetted application is planning, uses an adaptation of PC-2. The most related work, worth comparing, is Decther et al.’s [1991], where, in particular, the authors show the equivalence between, on one hand, applying path-consistency to an STP and, on the other, applying an all-to-all shortest paths algorithm, such as Floyd-Warshall’s [Aho et al., 1976; Papadimitriou and Steiglitz, 1982], to the corresponding distance graph. Dechter et al. [1991], as explained in the introduction, didn’t focus on node- and arc-consistencies, because the adding of an ”origin of the world” variable led them to the conclusion that a TCSP was already node- and arc-consistent. In the present work, we have looked at the constraints between the ”origin of the world” variable and the other variables, as the binarized domains of these other variables. This led us to the definition of the notion of binarized-domains Arc-Consistency, which is computationally one factor less expensive. We showed, in particular, that applying bdArcConsistency to an STP was equivalent to applying a one-to-all all-to-one shortest paths algorithm to the corresponding rooted distance graph. The bdArc-Consistency algorithm we have defined, bdAC-3, detects negative circuits reachable from  X0, or from which  X0is reachable. Another related work is Schwalb and Dechter’s [1997], where, in particular, the authors propose the use of weak versions of path-consistency as filtering procedures of general TCSP solvers. One of these weaker versions is ULT (Upper-Lower Tightning), in which composition is replaced with weak composition. We have discussed the use of a similar idea in a general TCSP solver with the filtering procedure consisting of a weak version of the binarized-domains ArcConsistency algorithm bdAC-3 proposed in this work. The rest of the section presents an adaptation to TCSPs of

the other local-consistency algorithms in [Mackworth, 1977], namely, the arc-consistency algorithm AC-1, and the path consistency algorithms PC-1 and PC-2; it also looks at the termination of these adaptations; and shows, in particular, that an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997] is not guaranteed to always terminate.

8.1 Adaptation to TCSPs of AC-1, PC-1 and PC-2

In addition to the bdAC-3 algorithm, we provide in Figures 9 and 10 adaptations to TCSPs of the other three local-consistency algorithms in [Mackworth, 1977]: the arc-consistency algorithm AC-1 and the two path-consistency algorithms PC-1 and PC-2. The adaptations are named, respectively, bdAC-1, PC-1 and PC-2. Like bdAC-3, when applied to an STP, bdAC-1 detects, if any, negative circuits reachable from  X0, or from which  X0is reachable, in the corresponding rooted distance graph; it makes the STP bdArc-Consistent otherwise. PC-1 and PC-2, when applied to an STP, both detect, if any, negative circuits in the corresponding distance graph; they make the STP path-consistent otherwise. Both of bdAC-1 and PC-2 use the condition on negative circuits one can extract from Theorem 3 (line 4 of the REVISE procedure of Figure 3, for bdAC-1; line 4 of the REVISEPC-2 procedure of Figure 10, for PC-2).

As already stated in Remark 3, we refer to the procedure REVISE of Figure 3 without its line 4 as REVISE−, and to the algorithm bdAC-3 (Figure 4) in which procedure REVISE is replaced with REVISE−as bdAC-3−. In addition to that, we refer to the procedure REVISEPC-2 of Figure 10 without its line 4 as REVISEPC-2−, to the algorithm bdAC-1 (Figure 9) in which procedure REVISE is replaced with REVISE−as bdAC-1−, and to the algorithm PC-2 (Figure 10) in which procedure REVISEPC-2 is replaced with REVISEPC-2−as PC-2−.

8.2 Termination of the adaptations

PC-1 proceeds by passes, and each pass considers all possible triples of variables. It is a ”literal” adaptation from [Mackworth, 1977], and is guaranteed to terminate and to detect, when applied to an STP, the presence of negative circuits in the corresponding distance graph. This is not the case for bdAC-1−and PC-2−, which, deprived of line 4 of Procedure REVISE for the former, and of line 4 of Procedure REVISEPC-2 for the latter, have no guarantee to terminate even when the input is an STP. Example 2 shows that bdAC-1−and PC-2−, which are ”literal” adaptations of Mackworth’s [1977] AC-1 and PC-2, respectively, are not guarateend to terminate.

Example 2 (non termination of bdAC-1−and PC-2−). We consider the STP P = (X, C) with:

1. X  = {X0, X1, X2, X3}and

2.  C = {c1: (X1 − X0) ∈[30, +∞), c2: (X2 − X1) ∈[−20, −10], c3: (X3 − X1) ∈ (−∞,4], c4: (X3 −X2) ∈[40, 50]}.

The rooted distance graph of P (see Figure 11) does have a negative ciruit that is not reachable from  X0, but from which

Input: The matrix representation of a TCSP P. Output: True, indicating that the TCSP has been made bdArc-consistent; or false, indicating that inconsistency of P has been detected. procedure bdAC-1(P){

image

3. CHANGE=false; 4. for each  (i, j) ∈ Q

5. if REVISE(i, j){%begin if1 6. if(P0i = ∅)return false;

7. CHANGE=true 8. }%end if1

9. until  ¬CHANGE 10. return true

11. }%end bdAC1

Input: The matrix representation of a TCSP P. Output: True, indicating that the TCSP has been made path-consistent; or false, indicating that inconsistency of P has been detected. procedure PC-1(P){

1. repeat 2. CHANGE=false;

3. for (k = 0 to n)

4. for (i, j = 0 to n){ 5. temp  = Pij ∩ Pik ⊗ Pkj;

6. if(temp = ∅)return false; 7. if(temp ̸= Pij){Pij = temp;CHANGE=true}

8. } 9. until  ¬CHANGE

image

Figure 9: The binarized-domains Arc-Consistency algorithm bdAC-1 and the Path-Consistency algorithm PC-1.

image

1. DELETE=false; 2. temp = Pij ∩ Pik ⊗ Pkj;

3. if(temp  ̸= Pij){4. if[temp  ̸= ∅and (lowerB(temp) > −path-lb(P)

or upperB(temp) < path-lb(P))]temp  = ∅; 5. Pij =temp;Pji =temp⌣;

6. DELETE=true 7. }

8. return DELETE 9. }

image

Output: True, indicating that the TCSP has been made path-consistent; or false, indicating that inconsistency of P has been detected.

image

(Pik ⊂ IR)and  (Pkj ⊂ IR)}; 2. Emptydomain = false;

3. while  (Q ̸= ∅and (not Empty

4. select and delete a triple (i, k, j) from Q; 5. if REVISEPC-2(i, k, j)

6. if  (Pij = ∅)Emptydomain = true 7. else Q  = Q∪

{(i, j, m) : (i < m) and  (m ̸= j)and Pjm ⊂ IR}∪{(m, i, j) : (m < j) and  (m ̸= i)and Pmi ⊂ IR}

image

10. } %end PC2

Figure 10: The path-consistency algorithm PC-2 and the boolean procedure REVISEPC-2 it makes use of.

image

Figure 11: The distance graph of the STP of Example 2.

X0is reachable. bdAC-1 and bdAC-1−proceed by passes, each of which is guaranteed to terminate since it considers at most once each ordered pair  (Xi, Xj)such that there is a constraint on  Xiand  Xj. Each of the two versions of bdArcConsistency terminates when, either a binarized domain becomes empty, or a whole pass makes no change in the binarized domains. But for the version bdAC-1−, the order in which the pairs in its queue are propagated might make it impossible for the two terminating conditions to occur. Initially, the binarized domains are as follows:  P01 = [30, +∞), P02 = IRand  P03 = IR. For each of the two versions, we suppose that each of its passes propagates the pairs on which there is a constraint in the order  (X1, X2), (X1, X3), (X2, X1), (X2, X3), (X3, X1), (X3, X2). For both versions, the evolution of the binarized domains for the first three passes are as follows:

1. after Pass 1:  P01= [30, +∞),  P02= [10, +∞) and P03= [50, +∞)

2. after Pass 2:  P01= [46, +∞),  P02= [26, +∞) and P03= [66, +∞)

3. after Pass 3:  P01= [62, +∞),  P02= [42, +∞) and P03= [82, +∞)

This means that each pass increases the (finite) lower bound of each binarized domain by 16, which corresponds to the absolute value of the weight of the negative circuit (X1, X3, X2, X1). Given that path-lb(P) = −80, bdAC-1 will detect the negative circuit after the third pass. However, bdAC-1−will fail to do so, and will not terminate.

Let’s now look at how the two adaptations PC-2 and PC-2−of Mackworth’s [1977] PC-2 will behave on the STP. Keep in mind that their unique difference lies in line 4 of Procedure REVISEPC-2, which is absent in PC-2−. Both versions will initialise their queue as follows: Q = {(X0, X1, X2), (X0, X1, X3), (X1, X2, X3)}. We take the triple  (X0, X1, X2)for propagation. The resulting modifi-cations are as follows:

1.  P02= [10, +∞),  P20= (−∞, −10],

2. Q  = {(X0, X1, X3), (X1, X2, X3), (X0, X2, X1),

image

We then take the triple  (X0, X2, X3)for propagation. The modifications are as follows:

1.  P03= [50, +∞),  P30= (−∞, −50],

2. Q  = {(X0, X1, X3), (X1, X2, X3), (X0, X2, X1),

image

The situation of the binarized domains is now the same as that after Pass 1 of bdAC-1. We now repeat the following sequence: propagate triple  (X0, X3, X1), then triple  (X0, X1, X2), finally triple  (X0, X2, X3). Each pass of this repeat loop will increase by 16 the lower bound of each of the binarized domains. After the second pass, the binarized domain  P03becomes  [82, +∞), and PC-2 will then detect the presence of a negative circuit, and terminate. PC-2−, however, will keep repeating the loop indefinitely, and will not terminate. The details of the first two passes of the repeat loop are as follows:

image

We now summarise the discussion: Theorem 9. bdAC-1, PC-1 and PC-2 (Figures 9 and 10) always terminate.

Theorem 10. bdAC-1−, bdAC-3−and PC-2−are not guaranteed to terminate.

Finally, TCSP solution search algorithms using a binarized-domains arc consistency algorithm, such as bdAC-3, as the filtering procedure, are expected to drastically overcome general TCSP solvers [Dechter et al., 1991; Schwalb and Dechter, 1997] and TCSP-based schedulers [Belhadji and Isli, 1998] using path-consistency or a weak version of it as the filtering procedure. As a plausible explanation to this expected future for our newborn notion of binarized-domains arc-consistency, in the case of classical binary CSPs, arc-consistency algorithms and path-consistency algorithms, the first of which has a lower filtering power but is computationally cheaper, are both known since the seventies [Montanari, 1974; Mackworth, 1977], and the place of arc-consistency is known to be more advantageous than that of path-consistency as the filtering procedure of solution search algorithms.

We provided, and analysed the computational complexity of, an adaptation to TCSPs [Dechter et al., 1991] of Mackworth’s [1977] arc-consistency algorithm AC-3. A TCSP is closed under classical node- and arc-consistencies [Montanari, 1974; Mackworth, 1977], and we argued that this was certainly what made [Dechter et al., 1991] jump directly to the next local consistency algorithm, namely path- consistency. What made the adaptation possible was the look at the constraints of a TCSP between the ”origin of the world” variable and the other variables, as the binarized domains of these other variables.

For the convex part of TCSPs, namely STPs, we showed the equivalence between applying bdAC-3 to an STP, on one hand, and applying a one-to-all all-to-one shortest paths algorithm to its distance graph, on the other. We showed that the binarized domains of a connected bdArc-Consistent STP are minimal, and provided a polynomial backtrack-free procedure computing a solution to such an STP. Another polynomial backtrack-free procedure has been provided for the task of extracting, from a bdArc-Consistent STP, a connected bdArc-Consistent STP refinement, if the STP is consistent, or showing its inconsistency, otherwise.

We showed how to use bdAC-3 as the filtering procedure of a general TCSP solver, and of a TCSP-based job shop scheduler.

We also discussed how to adapt to TCSPs the other local-consistency algorithms in [Mackworth, 1977], namely, the arc-consistency algorithm AC-1, and the path consistency algorithms PC-1 and PC-2. In particular, this led us to the conclusion that an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997], contray to the adaptation we provided, is not guaranteed to always terminate.

To the best of our knowledge, the binarized-domains arc-consistency algorithm bdAC-3 we have investigated for general TCSPs is the very first of its kind, and we do hope and expect that it will have a positive impact on the near-future developments of the field. Points needing further investigation include improvement of the lower and upper bounds path-lb(P) and path-ub(P), as defined in this work for a TCSP P, as they are crucial for the bdAC-3 algorithm’s computational behaviour, and for that of search algorithms using bdAC-3 as the filtering procedure during the search.

An important future work that has always retained our attention, whose importance grows with the presented work, is to contribute to the addition of tools to Prolog libraries such as CLP(QI, IR); tools such as a TCSP solver and a TCSP-based job shop scheduler using bdArc-Consistency, or its weak version wbdArc-Consistency, as the filtering procedure during the search.

[Aho et al., 1976] A V Aho, J E Hopcroft, and J D Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., 1976.

[Allen, 1983] James Allen. Maintaining knowledge about temporal intervals. Communications of the Association for Computing Machinery, 26(11):832–843, 1983.

[Belhadji and Isli, 1998] S Belhadji and A Isli. Temporal constraint satisfaction techniques in job shop scheduling problem solving. Constraints, 3(2-3):203–211, 1998.

[Bellman, 1958] R Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.

[Bessi`ere et al., 1996] C Bessi`ere, A Isli, and G Ligozat. Global consistency in interval algebra networks: tractable subclasses. In W Wahlster, editor, Proceedings of the 12th European Conference on Artificial Intelligence (ECAI), pages 3–7, Budapest, 1996. John Wiley.

[Bessi`ere, 1996] C Bessi`ere. A simple way to improve path consistency processing in interval algebra networks. In William J. Clancey and Daniel S. Weld, editors, Proceedings of the 13th American Conference on Artificial Intelligence (AAAI), pages 375–380. AAAI Press / The MIT Press, 1996.

[Broxvall et al., 2002] Mathias Broxvall, Peter Jonsson, and Jochen Renz. Disjunctions, independence, refinements. Artif. Intell., 140(1/2):153–173, 2002.

[Carlier et al., 1985] J Carlier, P Chr´etienne, and C Girault. Modelling scheduling problems with timed petri nets. In G Rozenberg, H J Genrich, and G Roucairol, editors, Advances in Petri nets 1984, volume 188 of Lecture Notes in Computer Science, pages 62–84. Springer, 1985.

[Cervoni et al., 1994] R Cervoni, A Cesta, and A Oddi. Managing dynamic temporal constraint networks. In Proceedings of the Second International Conference on Arti-ficial Intelligence Planning Systems (AIPS), pages 13–18. AAAI Press, 1994.

[Cesta and Oddi, 1996] A Cesta and A Oddi. Gaining effi- ciency and flexibility in the simple temporal problem. In Proceedings of the Third International Workshop on Temporal Representation and Reasoning (TIME), pages 45– 50. IEEE Computer Society, 1996.

[Davis, 1989] E Davis. Private communication. 1989.

[Dechter et al., 1991] R Dechter, I Meiri, and J Pearl. Temporal constraint networks. Artificial Intelligence, 49:61– 95, 1991.

[Dechter, 1992] R Dechter. From local to global consistency. Artificial Intelligence, 55:87–107, 1992.

[Dincbas et al., 1990] M Dincbas, H Simonis, and P van Hentenryck. Solving large combinatorial problems in logic programming. Journal of Logic Programming, 8(1):75–93, 1990.

[Ford and Fulkerson, 1962] L R Ford and D R Fulkerson. Flows in Networks. Princeton University Press, New Jersey, 1962.

[Freuder, 1982] E C Freuder. A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery, 29:24–32, 1982.

[Isli, 2001] A Isli. On deciding Consistency for CSPs of Cyclic Time Intervals. In I Russel and J F Kolen, editors, Proceedings of the Fourteenth International Florida Arti-ficial Intelligence Research Society Conference (FLAIRS), pages 547–551, Key West, Florida, USA, May 21-23 2001. AAAI Press.

[Kautz and Ladkin, 1991] H Kautz and P Ladkin. Integrating metric and qualitative temporal reasoning. In Proceedings of the 9th American Conference on Artificial Intelligence

(AAAI), pages 241–246, Anaheim, CA, 1991. AAAI/MIT Press.

[Kong et al., 2018] S Kong, J H Lee, and S Li. Multiagent simple temporal problem: The arc-consistency approach. In Proceedings of the 32nd American Conference on Arti-ficial Intelligence (AAAI), pages 6219–6226. AAAI Press, 2018.

[Ladkin and Maddux, 1994] P Ladkin and R Maddux. On binary Constraint Problems. Journal of the Association for Computing Machinery, 41(3):435–469, 1994.

[Ladkin and Reinefeld, 1992] P Ladkin and A Reinefeld. Ef- fective solution for qualitative constraint problems. Artifi-cial Intelligence, 57:105–124, 1992.

[Ligozat, 1996] Gerard Ligozat. A new proof of tractability for ord-horn relations. In William J. Clancey and Daniel S. Weld, editors, Proceedings of the 13th American Conference on Artificial Intelligence (AAAI), pages 395–401. AAAI Press / The MIT Press, 1996.

[Mackworth, 1977] A K Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99–118, 1977.

[Montanari, 1974] U Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Sciences, 7:95–132, 1974.

[Moore, 1959] E F Moore. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957), page 285–292, Cambridge, 1959. Harvard University Press.

[Nebel and B¨urckert, 1995] Bernhard Nebel and HansJ¨urgen B¨urckert. Reasoning about temporal relations: A maximal tractable subclass of allen’s interval algebra. J. ACM, 42(1):43–66, 1995.

[Nebel, 1997] Bernhard Nebel. Solving hard qualitative tem- poral reasoning problems: Evaluating the efficiency of using the ord-horn class. Constraints An Int. J., 1(3):175– 190, 1997.

[Papadimitriou and Steiglitz, 1982] C H Papadimitriou and K Steiglitz. Combinatorial Optimisation: Algorithms and Complexity. 1982.

[Planken et al., 2008] L Planken, M de Weerdt, and R van der Krogt. P3C: A new algorithm for the simple temporal problem. In Proceedings of the 18th International Conference on Automated Planning and Scheduling ICAPS, pages 256–263. AAAI Press, 2008.

[Pratt, 1977] V R Pratt. Two easy theories whose combina- tion is hard. Technical report, Massachusetts Institute of Technology, 1977.

[Sadeh et al., 1995] N Sadeh, K Sycara, and Y Xiong. Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 76:455–480, 1995.

[Schwalb and Dechter, 1997] E Schwalb and R Dechter. Processing disjunctions in temporal constraint networks. Artificial Intelligence, 193:29–61, 1997.

[Shostak, 1981] R E Shostak. Deciding linear inequalities by computing loop residues. J. ACM, 28(4):769–779, 1981.

[Stergiou and Koubarakis, 2000] K Stergiou and M Koubarakis. Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence, 120(1):81–117, 2000.

[van Beek and Manchak, 1996] Peter van Beek and Den- nis W. Manchak. The design and experimental analysis of algorithms for temporal reasoning. J. Artif. Intell. Res., 4:1–18, 1996.

[van Beek, 1992] Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence, 58(1-3):297–326, 1992.

The worst-case computational complexity of the three operations of converse, intersection and composition are as follows:

1. If  Cikand  Ckjare convex sets (intervals) then their composition  Cikj = Cik ⊗ Ckjis convex:

(a) the lower (respectively, upper) bound of  Cikjis the sum of the lower (respectively, upper) bounds of Cikand  Ckj;

(b)  Cikjis left-closed (respectively, right-closed) if both  Cikand  Ckjare left-closed (respectively, right-closed), it is left-open (respectively, rightopen) otherwise.

As an example,  (−41, 20]⊗ [55, 60] = (−41 + 55, 20+60] = (14, 80]. We need therefore two operations of addition to perfom the composition of two convex sets, whose worst-case computational complexity is thus O(1).

2. If  C1ijand  C2ijare convex sets then their intersection A = C1ij ∩ C2ijis obtained by comparing the bounds of  C1ijwith those of  C2ij: its worst-case computational complexity is thus O(1).

3. If  Cijis a convex set then its converse  C⌣ijis obtained by negating the bounds of  Cij: its computational complexity is thus also O(1).

4. Therefore:

(a) If  Cikand  Ckjare unions of convex sets with |mPcs(Cik)| = n1and |mPcs(Ckj)| = n2, the worst-case computational complexity of their composition is  O(n1n2);

(b) If  C1ijand  C2ijare unions of convex sets with |mPcs(C1ij)| = n1and |mPcs(C2ij)| = n2, the worst-case computational complexity of their intersection is  O(n1 + n2);

(c) If  Cijis a union of convex sets with |mPcs(Cij)| =n, the worst-case computational complexity of its converse is O(n).

image

Figure 12: The distance graphs of the STPs of Appendices B (left) and C (Right). The edges  (Xi, Xj)whose weights are infinite and the loops  (Xi, Xi)are not shown.

Let P = (X, C) be the following STP, whose distance graph is given by Figure 12(Left):

image

We apply the bdArc-Consistency algorithm bdAC-3 to P. The initial binarized domains of the variables and the initialisation of the queue Q are as follows:

1.  Q = {(X1, X2), (X2, X1), (X2, X3), (X3, X2), (X3, X4),(X4, X3)}

2. Xi

image

We take in turn the pairs in Q for propagation. When a pair  (Xi, Xj), with  ij ̸= 0, is taken from Q for propagation, we apply the path-consistency operation on triangle (X0, Xj, Xi): P0i = P0i ∩ P0j ⊗ Pji. If  P0iis modified, the pairs  (Xk, Xi)such that  k ̸= 0, k ̸= i, k ̸= jand P has a constraint on  Xkand  Xi, that are no longer in Q, reenter the queue. bdAC-3 will terminate when a binarized domain becomes empty, indicating inconsistency of the initial STP, or the queue becomes empty, indicating that the STP has been made bdArc-Consistent.

image

path-consistency operation on triangle  (X0, X2, X1):

image

Step 3: we take the pair  (X2, X3):

image

The queue Q is empty, and no (binarized) domain has become empty. bdAC-3 terminates and the resulting STP is bdArcConsistent. The minimal (binarized) domains of variables X1, X2, X3, X4are, respectively, [10, 20], [40, 50], [20, 30] and [60, 70]. Therefore, if we consider the distance graph of the original STP, we have the following:

1. the distances of the shortest paths from  X0to X1, X2, X3, X4are, respectively, 20, 50, 30 and 70

2. the distances of the shortest paths from each of X1, X2, X3, X4to  X0are, respectively,  −10, −40, −20and  −60.

In the STP of the example in Appendix B, we replace constraint  c3with  (X2 − X1) ∈ [30, +∞), remove constraint  c2, and add the constraint  (X4 − X2) ∈ (−∞, 4]. We get the STP P = (X, C), whose distance graph is given by Figure 12(Right):

1. X  = {X0, X1, X2, X3, X4}and

2.  C = {c1: (X1 − X0) ∈[10, 20], c2: (X2 − X1) ∈[30, +∞), c3: (X3 − X2) ∈ [−20, −10], c4: (X4 −X2) ∈ (−∞,4], c5: (X4 − X3) ∈[40, 50]}.

The rooted distance graph of P does have a negative ciruit that is not reachable from  X0, but from which  X0is reachable. The proposed algorithm, contrary to Bellman-Ford-Moore’s, will detect the negative circuit; this amounts to detecting the inconsistency of the STP.

We apply the bdArc-Consistency algorithm bdAC-3 to P. The initial binarized domains of the variables and the initialisation of the queue Q are as follows:

1. Q  = {(X1, X2), (X2, X1), (X2, X3), (X3, X2), (X2, X4), (X4, X2), (X3, X4), (X4, X3)}

2. Xi

image

We take in turn the pairs in Q for propagation. When a pair  (Xi, Xj), with  ij ̸= 0, is taken from Q for propagation, we apply the path-consistency operation on triangle (X0, Xj, Xi): P0i = P0i ∩ P0j ⊗ Pji. If  P0iis modified, the pairs  (Xk, Xi)such that  k ̸= 0, k ̸= i, k ̸= jand P has a constraint on  Xkand  Xi, that were but are no longer in Q, reenter the queue. bdAC-3 will terminate when a binarized domain becomes empty, indicating inconsistency of the initial STP, or the queue becomes empty, indicating that the STP has been made bdArc-Consistent.

Step 1: we take the pair  (X2, X1):

1.  P02 = P02 ∩ P01 ⊗ P12= IR  ∩[10, 20]  ⊗[30, +∞) = [40, +∞)

2. There is modification, and the new configuration is:

Q = {(X1, X2), (X2, X3), (X3, X2), (X2, X4), (X4, X2), (X3, X4), (X4, X3)}

image

Step 2: we take the pair  (X2, X3):

1.  P02 = P02 ∩ P03 ⊗ P32= [40, +∞) ∩IR  ⊗[10, 20] = [40, +∞)

2. No modification, and the new configuration is:

Q = {(X1, X2), (X3, X2), (X2, X4), (X4, X2), (X3, X4), (X4, X3)}

image

Step 3: we take the pair  (X3, X2):

1.  P03 = P03∩P02⊗P23= IR∩[40, +∞)⊗[−20, −10] = [20, +∞)

2. There is modification, and the new configuration is:

Q = {(X1, X2), (X2, X4), (X4, X2), (X3, X4), (X4, X3)}

image

Step 4: we take the pair  (X2, X4):

1.  P02 = P02 ∩P04 ⊗P42= [40, +∞)∩IR⊗[−4, +∞) = [40, +∞)

2. No modification, and the new configuration is:

image

Step 5: we take the pair  (X4, X2):

1.  P04 = P04∩P02⊗P24= IR∩[40, +∞)⊗(−∞,4] = IR

2. No modification, and the new configuration is:

image

Step 6: we take the pair  (X3, X4):

1.  P03 = P03∩P04⊗P43= [20, +∞)∩IR⊗[−50, −40] = [20, +∞)

2. No modification, and the new configuration is:

image

Step 7: we take the pair  (X4, X3):

1.  P04 = P04 ∩ P03 ⊗ P34= IR  ∩[20, +∞) ⊗[40, 50] = [60, +∞)

2. There is modification.  (X2, X4)reenters the queue, and the new configuration is:

image

Step 8: we take the pair  (X2, X4):

1.  P02 = P02 ∩ P04 ⊗ P42= [40, +∞) ∩[60, +∞) ⊗[−4, +∞) = [56, +∞)

2. There is modification, and the new configuration is:

The pair  (X3, X2)reenters the queue Q, which becomes Q = {(X1, X2), (X3, X2)}

image

Step 9: we take the pair  (X3, X2):

1.  P03 = P03 ∩ P02 ⊗ P23= [20, +∞) ∩[56, +∞) ⊗[−20, −10] = [36, +∞)

2. There is modification, and the new configuration is: The pair  (X4, X3)reenters the Q, which becomes Q = {(X1, X2), (X4, X3)}

image

The pair  (X2, X4)reenters the Q, which becomes Q = {(X1, X2), (X2, X4)}

Xi

Step 11: we take the pair  (X2, X4):

image

The pair  (X3, X2)reenters the queue Q, which becomes Q = {(X1, X2), (X3, X2)}

image

Step 12: we take the pair  (X3, X2):

1.  P03 = P03 ∩ P02 ⊗ P23= [36, +∞) ∩[72, +∞) ⊗[−20, −10] = [52, +∞)

2. There is modification, and the new configuration is: The pair  (X4, X3)reenters the queue Q, which becomes Q = {(X1, X2), (X4, X3)}

image

2. There is modification of  P04with  −lowerB(P04) =−92strictly smaller than path-lb(P) = −90. The conditions of Theorem 3 get violated, and the situation corresponds to a detection of a negative circuit. The algorithm terminates with a negative answer to the consistency problem of P (line 4 of the REVISE procedure of Figure 3).


Designed for Accessibility and to further Open Science