3.7.252. Sweep

A constraint for which the filtering algorithm may use a sweep algorithm. A sweep algorithmΒ [PreparataShamos85] solves a problem by moving an imaginary object (usually a line, a plane or sometime a point). The object does not move continuously, but only at particular points where we actually do something. A sweep algorithm uses the following two data structures:

  • A data structure called the sweep status, which contains information related to the current position of the object that moves,

  • A data structure named the event point series, which holds the events to process.

The algorithm initialises the sweep status for the initial position of the imaginary object. Then the object jumps from one event to the next event; each event is handled by updating the status of the sweep.

A first typical application reported inΒ [BeldiceanuCarlsson01sweep] of the idea of sweep within the context of constraint programming is to aggregate several constraints that have two variables in common in order to perform more deduction. Let:

  • πš‡ and 𝚈 be two distinct variables,

  • C 1 (πš… 11 ,β‹―,πš… 1n 1 ),β‹―,C m (πš… m1 ,β‹―,πš… mn m ) be a set of m constraints such that all constraints mention πš‡ and 𝚈.

The sweep algorithm tries to adjust the minimum value of πš‡ with respect to the conjunction of the previous constraints by moving a sweep-line from the minimum value of πš‡ to its maximum value. It accumulates within the sweep-line status the values to be currently removed from the domain of 𝚈. If, for the current position Ξ” of the sweep-line, all values of 𝚈 have to be removed, then the algorithm removes value Ξ” from the domain of πš‡. The events to process correspond to the starts and ends of forbidden two-dimensional regions with respect to constraints C 1 ,β‹―,C m and variables πš‡ and 𝚈. Forbidden regions are a way to represent constraints C 1 ,β‹―,C m that is suited for this sweep algorithm. A forbidden region of the constraint C i with respect to the variables πš‡ and 𝚈 is an ordered pair ([F x - ,F x + ],[F y - ,F y + ]) of intervals such that: βˆ€x∈[F x - ,F x + ],βˆ€y∈[F y - ,F y + ]:C i (πš… i1 ,β‹―,πš… in i ) has no solution in which πš‡=x and 𝚈=y.

FigureΒ 3.7.78 shows five constraints and their respective forbidden regions (in pink) with respect to two given variables πš‡ and 𝚈 and their domains. The first constraint requires that πš‡, 𝚈 and 𝚁 be pairwise distinct. ConstraintsΒ (B,C) are usual arithmetic constraints.Within the context of continuous variables, Chabertet al.Β [ChabertBeldiceanu10] shows how to compute a forbidden region that contains a given unfeasible point for numerical constraints with arbitrary mathematical expressions. ConstraintΒ (D) can be interpreted as requiring that two rectangles of respective origins (πš‡,𝚈) and (πšƒ,πš„) and sizes (2,4) and (3,2) do not overlap. Finally, constraintΒ (E) is a parity constraint of the sum of πš‡ and 𝚈.

Figure 3.7.78. Examples of forbidden regions (in pink) according to the two variables πš‡ and 𝚈 (πš‡βˆˆ[0,4], 𝚈∈[0,4]) for five constraints

We illustrate the use of the sweep algorithm on a concrete example. Assume that we want to find out the minimum value of variable πš‡ with respect to the conjunction of the five constraints that were introduced by FigureΒ 3.7.78, that is versus the following conjunction of constraints:

πš‡βˆˆ0..4,𝚈∈0..4,𝚁∈0..9,πšƒβˆˆ0..2,πš„βˆˆ0..3πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš‡,𝚈,𝚁)(A)|πš‡-𝚈|>2(B)πš‡+2𝚈-1<πš‚(C)πš‡+1<πšƒβˆ¨πšƒ+2<πš‡βˆ¨πšˆ+3<πš„βˆ¨πš„+1<𝚈(D)(πš‡+𝚈) mod 2=2(E)

FigureΒ 3.7.79 shows the content of the sweep-line status (i.e., the forbidden values for 𝚈 according the current position of the sweep-line) for different positions of the sweep-line. More precisely, the sweep-line status can be viewed as an array (see the rightmost part of FigureΒ 3.7.79) which records for each possible value of 𝚈 the number of forbidden regions that currently intersect the sweep-line (see the leftmost part of FigureΒ 3.7.79 where these forbidden regions are coloured in red). The smallest possible value of πš‡ is 4, since this is the first position of the sweep-line where the sweep-line status contains a value of 𝚈 which is not forbidden (i.e.,Β πš‡=4, 𝚈=0 is not covered by any forbidden region).

Figure 3.7.79. Sweep-line status while sweeping through the potential values of variable πš‡ (i.e., values from 0 to 4) until a potentially feasible point πš‡=4, 𝚈=4 wrt the five constraintsΒ (A), (B), (C), (D) and (E) is found; the sweep-line status (i.e.,Β the rightmost column) records for a potential value v of variable πš‡ and for each potential value w of variable 𝚈 how many constraints are violated when both πš‡=v and 𝚈=w.

A second similar application of the idea of sweep in the context of the cardinality operatorΒ [VanHentenryckDeville91], where all constraints have at least two variables in common, is reported inΒ [BeldiceanuCarlssonSoftSweep01]. As before, each constraint C of the cardinality operator is defined by its forbidden regions with respect to a pair of variables (πš‡,𝚈) that occur in every constraint. In addition to that, a constraint C is also defined by its safe regions, where a safe region is the set of assignments to the pair (πš‡,𝚈) located in a rectangle such that the constraint always holds, no matter which values are taken by the other variables of C. Then the extended sweep algorithm filters the pair of variables (πš‡,𝚈) right from the beginning according to the minimum and maximum number of constraints of the cardinality operator that have to hold.

A third typical application reported inΒ [BeldiceanuCarlssonPoderSadekTruchet07] and inΒ [CarlssonBeldiceanuMartin08] of the idea of sweep within the context of multi-dimensional Β placement problems (see for instance the πšπš’πšπšπš— and the 𝚐𝚎𝚘𝚜𝚝 constraints) for filtering each coordinate of the origin of an object o to place is as follows. To adjust the minimum (respectively maximum) value of a coordinate of the origin we perform a recursive traversal of the Β placement space in increasing (respectively decreasing) lexicographic order and skips infeasible points that are located in a multi-dimensional forbidden set. Each multi-dimensional forbidden set is computed from a constraint where object o occurs (for instance a non-overlapping constraint in the context of the πšπš’πšπšπš— and the 𝚐𝚎𝚘𝚜𝚝 constraints).