[BeldiceanuContejean94]

$\mathrm{𝚍𝚒𝚏𝚏𝚗}\left(\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}\right)$

$\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}$, $\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\mathtt{1}$, $\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\mathtt{2}$, $\mathrm{𝚍𝚒𝚏𝚏}\mathtt{2}$.

Figure 5.118.1 represents the position of the three rectangles of the example. The coordinates of the leftmost lowest corner of each rectangle are stressed in bold. The $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint holds since the three rectangles do not overlap as explained in Figure 5.118.2.

Figure 5.118.1. Illustration of the Example slot: the three rectangles

Figure 5.118.2. Illustration of the Example slot: the reasons (A), (B), (C) why the pairs of rectangles $(R_1,R_2)$, $(R_1,R_3)$, $(R_2,R_3)$ do not overlap

Figure 5.118.3 gives all solutions to the following non ground instance of the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint:

$X_1\in [1,3]$, ${\mathrm{𝐸𝑋}}_1\in [1,9]$, $Y_1\in [1,3]$, ${\mathrm{𝐸𝑌}}_1\in [1,9]$,

$X_2\in [1,3]$, ${\mathrm{𝐸𝑋}}_2\in [1,9]$, $Y_2\in [2,3]$, ${\mathrm{𝐸𝑌}}_2\in [1,9]$,

$X_3\in [1,2]$, ${\mathrm{𝐸𝑋}}_3\in [1,9]$, $Y_3\in [1,4]$, ${\mathrm{𝐸𝑌}}_3\in [1,9]$,

$X_4\in [1,3]$, ${\mathrm{𝐸𝑋}}_4\in [1,9]$, $Y_4\in [1,3]$, ${\mathrm{𝐸𝑌}}_4\in [1,9]$,

$\mathrm{𝚍𝚒𝚏𝚏𝚗}$$(\langle \langle X_{1}2{\mathrm{𝐸𝑋}}_1,Y_{1}3{\mathrm{𝐸𝑌}}_1\rangle ,\langle X_{2}3{\mathrm{𝐸𝑋}}_2,Y_{2}2{\mathrm{𝐸𝑌}}_2\rangle ,$

         $\langle X_{3}1{\mathrm{𝐸𝑋}}_3,Y_{3}4{\mathrm{𝐸𝑌}}_3\rangle ,\langle X_{4}4{\mathrm{𝐸𝑋}}_4,Y_{4}1{\mathrm{𝐸𝑌}}_4\rangle \rangle )$.

Figure 5.118.3. All solutions corresponding to the non ground example of the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint of the All solutions slot

• Items of $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}$ are permutable.

• Items of $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}.\mathrm{𝚘𝚛𝚝𝚑}$ are permutable (same permutation used).

• $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}.\mathrm{𝚘𝚛𝚝𝚑}.\mathrm{𝚜𝚒𝚣}$ can be decreased to any value $\ge 0$.

• One and the same constant can be added to the $\mathrm{𝚘𝚛𝚒}$ and $\mathrm{𝚎𝚗𝚍}$ attributes of all items of $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}.\mathrm{𝚘𝚛𝚝𝚑}$.

Contractible wrt. $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}$.

The $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint occurs in placement and scheduling problems. It was for instance used for scheduling problems where one has to both assign each non-preemptive task to a resource and fix its origin so that two tasks, which are assigned to the same resource, do not overlap. When the resource is a set of persons to which non-preemptive tasks have to be assigned this corresponds to so called timetabling problems. A second practical application from the area of the design of memory-dominated embedded systems [Szymanek04] can be found in [SzymanekKuchcinski01]. Together with arithmetic and $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraints, the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint was used in [Szczygiel01] for packing more complex shapes such as angles. Figure 5.118.4 illustrates the angle packing problem on an instance involving 10 angles taken from [Szczygiel01].

Figure 5.118.4. A solution for the angle packing problem of items $A_1=[2,4,3,1]$, $A_2=[2,2,1,3]$, $A_3=[1,3,3,2]$, $A_4=[2,1,4,3]$, $A_5=[1,7,2,2]$, $A_6=[1,2,5,5]$, $A_7=[6,2,2,3]$, $A_8=[4,2,2,1]$, $A_9=[3,1,1,4]$, $A_{10}=[3,2,1,1]$.

One other packing problem attributed to S. Golomb is to find the smallest square that can contain the set of consecutive squares from $1\times 1$ up to $n\times n$ so that these squares do not overlap each other (see the smallest rectangle area problem).

Unlike the definition of the Purpose slot the original paper [BeldiceanuContejean94] introducing the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint imposes all orthotopes sizes to be different from 0. But it is convenient to allow variable sizes which can be assigned value 0 to model the fact that an orthotope can be skipped.

When we have segments (respectively rectangles) the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint is referenced under the name $\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\mathtt{1}$ (respectively $\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\mathtt{2}$) in SICStus Prolog [Sicstus95]. When we have rectangles the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint is also called $\mathrm{𝚍𝚒𝚏𝚏}\mathtt{2}$ in JaCoP. In MiniZinc (http://www.minizinc.org/) the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint considers only rectangles.

It was shown in [Thiel04] that, finding out whether a non-overlapping constraint between a set of rectangles has a solution or not is NP-hard. This was achieved by reduction from sequencing with release times and deadlines.

In the two-dimensional case, when rectangles heights are all equal to one and when rectangles starts in the first dimension are all fixed, the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint can be rewritten as a $𝚔\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint corresponding to a system of $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints derived from the maximum cliques of the corresponding interval graph.

Checking whether a $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint for which all variables are fixed is satisfied or not is related to the Klee's measure problem: given a collection of axis-aligned multi-dimensional boxes, how quickly can one compute the volume of their union. Then the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint holds if the volume of the union is equal to the sum of the volumes of the different boxes.

A first possible method for filtering non zero size orthotopes is to use constructive disjunction. The idea is to try out each alternative of a disjunction (e.g., given two orthotopes $o_1$ and $o_2$ that should not overlap, we successively assume for each dimension that $o_1$ finishes before $o_2$, and that $o_2$ finishes before $o_1$) and to remove values that were pruned in all alternatives. For the two-dimensional case of $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ a second possible solution used in [RochonDuVerdier92] is to represent explicitly the two-dimensional domain of the origin of each rectangle by a quadtree [Samet89] and to accumulate all forbidden regions within this data structure. As for conventional domain variables, a failure occurs when a two-dimensional domain get empty. A third possible filtering algorithm based on sweep is described in [BeldiceanuCarlsson01sweep].

The thesis of J. Nelissen [Nelissen94] considers the case where all rectangles have the same size and can be rotated from 90 degrees (i.e., the pallet loading problem.). For the $n$-dimensional case of $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ a filtering algorithm handling the fact that two objects do not overlap is given in [BeldiceanuGuoThiel01].

Figure 5.118.5. A hard instance from [Nelissen94]: A solution for packing 99 rectangles of size $5\times 9$ into a rectangle of size $86\times 52$

Extensions of the non-overlapping constraint to polygons and to more complex shapes are respectively described in  [BeldiceanuGuoThiel01] and in [RibeiroCarravilla04]. Specialised propagation algorithms for the squared squares problem [BouwkampDuijvestijn92] (based on the fact that no waste is permitted) are given in [Gambini99a] and in [Gambini99b].

The $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint can be used as a necessary condition for the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint. Figure 5.118.6 illustrates this point for the two-dimensional case. A first (respectively second) $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint is obtained by forgetting the $y$-coordinate (respectively the $x$-coordinate) of the origin of each rectangle occurring in a $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint. Parts (B) and (C) respectively depict the cumulated profiles associated with the projection of the rectangles depicted by part (A) on the $x$ and $y$ axes.

The $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint is a necessary but not sufficient condition for the two-dimensional case of the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint. Figure 5.118.7 illustrates this point on an example taken from [Biro90] where one has to place the 8 rectangles $R_1$, $R_2$, $R_3$, $R_4$, $R_5$, $R_6$, $R_7$, $R_8$ of respective size $5\times 2$, $8\times 2$, $6\times 1$, $5\times 1$, $2\times 1$, $3\times 1$, $2\times 2$ and $1\times 2$ in a big rectangle of size $12\times 4$. As shown by Figure 5.118.7 there is a cumulative solution where $R_8$ is split in two parts but M. Hujter proves in [Hujter90] that there is no solution where no rectangle is split.

Figure 5.118.6. Looking from the perspective of the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint in a two-dimensional rectangles placement problem: projecting the three rectangles of (A) on the $x$ axis (B) and on the $y$ axis (C)

Figure 5.118.7. Illustrating the necessary but not sufficient placement condition: the rectangle $R_8$ is split in two parts

In the context of $n$ parallelepipeds that have to be packed [GehringMenschnerMeyer90], [LiCheng90] within a box of sizes $X\times Y\times Z$ one can proceed as follows for stating three $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraints. The $i^{th}$ (with $i\in [1,n]$) parallelepiped is described by the following attributes:

• ${\mathrm{𝑜𝑥}}_i$, ${\mathrm{𝑜𝑦}}_i$, ${\mathrm{𝑜𝑧}}_i$ (with $i\in [1,n]$) the coordinates of its origin on the $x$, $y$ and $z$-axes.

• ${\mathrm{𝑠𝑥}}_i$, ${\mathrm{𝑠𝑦}}_i$, ${\mathrm{𝑠𝑧}}_i$ (with $i\in [1,n]$) its sizes on the $x$, $y$ and $z$-axes.

• ${\mathrm{𝑝𝑥}}_i$, ${\mathrm{𝑝𝑦}}_i$, ${\mathrm{𝑝𝑧}}_i$ (with $i\in [1,n]$) the surfaces of its projections onto the planes $yz$, $xz$, and $xy$ respectively equal to ${\mathrm{𝑠𝑦}}_i{\mathrm{𝑠𝑧}}_i$, ${\mathrm{𝑠𝑥}}_i{\mathrm{𝑠𝑧}}_i$, and ${\mathrm{𝑠𝑥}}_i{\mathrm{𝑠𝑦}}_i$.

• ${𝑣}_i$ its volume (equal to ${\mathrm{𝑠𝑥}}_i{\mathrm{𝑠𝑦}}_i{\mathrm{𝑠𝑧}}_i$).

For the placement of $n$ parallelepipeds we get the following necessary conditions that respectively correspond to three $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraints on the planes $yz$, $xz$, and $xy$:

$\left\{\begin{array}{c}\forall i\in [1,X]:{\sum }_{j\mid {\mathrm{𝑜𝑥}}_j\le i\le {\mathrm{𝑜𝑥}}_j+{\mathrm{𝑠𝑥}}_j-1}{\mathrm{𝑝𝑥}}_j\le YZ\\ \forall i\in [1,Y]:{\sum }_{j\mid {\mathrm{𝑜𝑦}}_j\le i\le {\mathrm{𝑜𝑦}}_j+{\mathrm{𝑠𝑦}}_j-1}{\mathrm{𝑝𝑦}}_j\le XZ\\ \forall i\in [1,Z]:{\sum }_{j\mid {\mathrm{𝑜𝑧}}_j\le i\le {\mathrm{𝑜𝑧}}_j+{\mathrm{𝑠𝑧}}_j-1}{\mathrm{𝑝𝑧}}_j\le XY\end{array}\right.$

Based on the fact that two orthotopes do not overlap if there exists at least one dimension where their projections do not overlap one can reformulate the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$$\left(\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}\right)$ constraint as a disjunction of inequalities between the origin and the end attributes. In addition one has to link the origin, the size and the end attributes of each orthotope in each dimension.

If we consider the example described in the Example slot we get the following reformulation:

• $4=2+2$ (link between the origin, size and end in dimension 1 of the first orthotope),

• $4=1+3$ (link between the origin, size and end in dimension 2 of the first orthotope),

• $8=4+4$ (link between the origin, size and end in dimension 1 of the second orthotope),

• $6=3+3$ (link between the origin, size and end in dimension 2 of the second orthotope),

• $11=9+2$ (link between the origin, size and end in dimension 1 of the third orthotope),

• $7=4+3$ (link between the origin, size and end in dimension 2 of the third orthotope),

• $4\le 4\vee 8\le 2\vee 4\le 3\vee 6\le 1$ (non-overlapping between the first and second orthotopes),

• $4\le 9\vee 11\le 2\vee 4\le 4\vee 7\le 1$ (non-overlapping between the first and third orthotopes),

• $8\le 9\vee 11\le 4\vee 6\le 4\vee 7\le 3$ (non-overlapping between the second and third orthotopes).

geost in Choco, nooverlap in Gecode, diff2 in JaCoP, diff in JaCoP, disjoint in JaCoP, disjointconditional in JaCoP, diffn in MiniZinc.

$\mathrm{𝚍𝚒𝚏𝚏𝚗}\_\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}$, $\mathrm{𝚍𝚒𝚏𝚏𝚗}\_\mathrm{𝚒𝚗𝚌𝚕𝚞𝚍𝚎}$, $\mathrm{𝚙𝚕𝚊𝚌𝚎}\_\mathrm{𝚒𝚗}\_\mathrm{𝚙𝚢𝚛𝚊𝚖𝚒𝚍}$.

common keyword: $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ (multi-site employee scheduling with calendar constraints,

scheduling with machine choice, calendars and preemption), $\mathrm{𝚍𝚒𝚏𝚏𝚗}\_\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}$, $\mathrm{𝚍𝚒𝚏𝚏𝚗}\_\mathrm{𝚒𝚗𝚌𝚕𝚞𝚍𝚎}$ (geometrical constraint,orthotope), $\mathrm{𝚐𝚎𝚘𝚜𝚝}$, $\mathrm{𝚐𝚎𝚘𝚜𝚝}\_\mathrm{𝚝𝚒𝚖𝚎}$, $\mathrm{𝚗𝚘𝚗}\_\mathrm{𝚘𝚟𝚎𝚛𝚕𝚊𝚙}\_\mathrm{𝚜𝚋𝚘𝚡𝚎𝚜}$ (geometrical constraint,non-overlapping), $\mathrm{𝚟𝚒𝚜𝚒𝚋𝚕𝚎}$ (geometrical constraint).

implied by: $\mathrm{𝚘𝚛𝚝𝚑𝚜}\_\mathrm{𝚊𝚛𝚎}\_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$.

implies: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ (implies one $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint for each dimension).

related: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}\_\mathrm{𝚝𝚠𝚘}\_𝚍$ ($\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}\_\mathrm{𝚝𝚠𝚘}\_𝚍$ is a necessary condition for $\mathrm{𝚍𝚒𝚏𝚏𝚗}$: forget one dimension when the number of dimensions is equal to 3), $\mathrm{𝚕𝚎𝚡}\_\mathrm{𝚌𝚑𝚊𝚒𝚗}\_\mathrm{𝚕𝚎𝚜𝚜}$, $\mathrm{𝚕𝚎𝚡}\_\mathrm{𝚌𝚑𝚊𝚒𝚗}\_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$ (lexicographic ordering on the origins of $\mathrm{𝚝𝚊𝚜𝚔𝚜}$, $\mathrm{𝚛𝚎𝚌𝚝𝚊𝚗𝚐𝚕𝚎𝚜}$, $...$), $\mathrm{𝚝𝚠𝚘}\_\mathrm{𝚘𝚛𝚝𝚑}\_\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}$, $\mathrm{𝚝𝚠𝚘}\_\mathrm{𝚘𝚛𝚝𝚑}\_\mathrm{𝚒𝚗𝚌𝚕𝚞𝚍𝚎}$.

specialisation: $\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚍𝚒𝚜𝚝}$ ($\mathrm{𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎}$ replaced by $\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, of same length), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ ($\mathrm{𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$), $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ ($\mathrm{𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎}$ replaced by $\mathrm{𝚝𝚊𝚜𝚔}$ with $\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ $\mathrm{𝚊𝚜𝚜𝚒𝚐𝚗𝚖𝚎𝚗𝚝}$ and $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}$ attributes), $\mathrm{𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎}$ (orthotope replaced by $\mathrm{𝚝𝚊𝚜𝚔}$ of $\mathrm{𝚑𝚎𝚒𝚐𝚝𝚑}$ 1), $𝚔\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (when rectangles heights are all equal to 1 and rectangles starts in the first dimension are all fixed), $\mathrm{𝚕𝚎𝚡}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ ($\mathrm{𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎}$ replaced by $\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛}$).

used in graph description: $\mathrm{𝚘𝚛𝚝𝚑}\_\mathrm{𝚕𝚒𝚗𝚔}\_\mathrm{𝚘𝚛𝚒}\_\mathrm{𝚜𝚒𝚣}\_\mathrm{𝚎𝚗𝚍}$, $\mathrm{𝚝𝚠𝚘}\_\mathrm{𝚘𝚛𝚝𝚑}\_\mathrm{𝚍𝚘}\_\mathrm{𝚗𝚘𝚝}\_\mathrm{𝚘𝚟𝚎𝚛𝚕𝚊𝚙}$.

application area: floor planning problem.

characteristic of a constraint: core.

combinatorial object: pentomino.

complexity: sequencing with release times and deadlines.

constraint arguments: business rules.

constraint type: decomposition, timetabling constraint, relaxation.

filtering: Klee measure problem, sweep, quadtree, compulsory part, constructive disjunction, SAT.

geometry: geometrical constraint, orthotope, polygon, non-overlapping.

heuristics: heuristics for two-dimensional rectangle placement problems.

modelling: disjunction, assignment dimension, assignment to the same set of values, assigning and scheduling tasks that run in parallel, relaxation dimension, sequence dependent set-up, multi-site employee scheduling with calendar constraints, scheduling with machine choice, calendars and preemption.

modelling exercises: assignment to the same set of values, assigning and scheduling tasks that run in parallel, relaxation dimension, sequence dependent set-up, multi-site employee scheduling with calendar constraints, scheduling with machine choice, calendars and preemption.

problems: strip packing, two-dimensional orthogonal packing, pallet loading.

puzzles: squared squares, packing almost squares, Partridge, pentomino, Shikaku, smallest square for packing consecutive dominoes, smallest square for packing rectangles with distinct sizes, smallest rectangle area, Conway packing problem.