AddNoOverlap2D for Bin-Packing in Time and Space

Model 2D non-overlap of rectangles using the AddNoOverlap2D global constraint. Apply it to 2D bin packing and to scheduling problems where tasks need both a time interval and a contiguous block of resource slots.

Step 1 of 157%

Tutorial

The AddNoOverlap2D Constraint

A rectangle in a constraint-programming model is a pair of intervals $(X_i, Y_i)$ , where

X_i = [s^x_i,\, e^x_i], \qquad Y_i = [s^y_i,\, e^y_i]

are its projections onto the $x$ - and $y$ -axes. The rectangle covers the region $X_i \times Y_i$ in the plane.

The AddNoOverlap2D constraint requires that for every pair of distinct rectangles $i \ne j$ ,

X_i \cap X_j = \emptyset \quad \text{or} \quad Y_i \cap Y_j = \emptyset.

Equivalently: two rectangles overlap in 2D iff both projections overlap in 1D.

Following the half-open scheduling convention, two 1D intervals $[a, b]$ and $[c, d]$ overlap iff

a < d \quad \text{and} \quad c < b.

Touching endpoints (e.g. $[0,3]$ and $[3,5]$ ) do not count as an overlap.

For instance, take

$R_1$ : $X_1 = [0, 3],\, Y_1 = [0, 2]$
$R_2$ : $X_2 = [2, 5],\, Y_2 = [3, 4]$

The $x$ -projections overlap on $[2, 3]$ , but the $y$ -projections are disjoint since $2 \le 3$ . One projection disjoint $\Rightarrow$ AddNoOverlap2D is satisfied.