Specifications PyCSP³ Tools Instances Competitions About

Constraint noOverlap

We start with the one dimensional form of noOverlap [H12] that corresponds to disjunctive [C82] and ensures that some tasks, defined by their origins and durations (lengths), must not overlap. The attribute zeroIgnored is optional (true, by default); when set to false, it indicates that zero-length tasks cannot be packed anywhere (cannot overlap with other tasks).

The semantics is given for zeroIgnored=false.

noOverlap($X$, $L$) with $X=\langle x_1,x_2,\ldots \rangle$ and $L=\langle l_1,l_2,\ldots \rangle$, iff $\forall (i,j) : 1 \leq i \lt j \leq |X|, x_i + l_i \leq x_j \vee x_j + l_j \leq x_i$

Syntax

<noOverlap  [ zeroIgnored="boolean" ]>
  <origins> (intVar wspace)2+ </origins>
  <lengths> (intVal wspace)2+ | (intVar wspace)2+ </lengths>
</noOverlap>

Example

<noOverlap>
  <origins> x1 x2 x3 </origins>
  <lengths> l1 l2 l3 </lengths>
</noOverlap>

The k-dimensional form of noOverlap corresponds to diffn [BC94] and ensures that, given a set of n-dimensional boxes; for any pair of such boxes, there exists at least one dimension where one box is after the other, i.e., the boxes do not overlap. The attribute zeroIgnored is optional (true, by default); when set to false, it indicates that zero-width boxes cannot be packed anywhere (cannot overlap with other boxes).

The semantics is given for zeroIgnored=false.

noOverlap($X$, $L$) with $X=\langle (x_{1,1},\ldots,x_{1,n}),(x_{2,1},\ldots,x_{2,n}),\ldots \rangle$ and $L=\langle (l_{1,1},\ldots,l_{1,n}),(l_{2,1},\ldots,l_{2,n}),\ldots \rangle$, iff $\forall (i,j) : 1 \leq i \lt j \leq |X|, \exists k \in 1..n : x_{i,k} + l_{i,k} \leq x_{j,k} \vee x_{j,k} + l_{j,k} \leq x_{i,k}$

Syntax

<noOverlap  [ zeroIgnored="boolean" ]>
  <origins> ("(" intVar ("," intVar)+ ")")2+ </origins>
  <lengths> 
    ("(" intVal ("," intVal)+ ")")2+ | ("(" intVar ("," intVar)+ ")")2+ 
  </lengths>
</noOverlap>

The following constraint enforces that all four 3-dimensional specified boxes do not overlap. The first box has origin (x1,y1,z1) and length (2,4,1), meaning that this box is situated from x1 to x1+2 on x-axis, from y1 to y1+4 on y-axis, and from z1 to z1+1 on z-axis.

Example

<noOverlap>
  <origins> (x1,y1,z1)(x2,y2,z2)(x3,y3,z3)(x4,y4,z4) </origins>  
  <lengths> (2,4,1)(4,2,3)(5,1,2)(3,3,2) </lengths>  
</noOverlap>