2

A rectangle $i$ can be represented by a tuple $(x_i, y_i, w_i,h_i)$ where

  • $x_i$ is the bottom left $x$-coordinate of rectangle $i$;
  • $y_i$ is the bottom left $y$-coordinate of rectangle $i$;
  • $w_i$ is the width of rectangle $i$;
  • $h_i$ is the height of rectangle $i$.

All values are integers and strictly positive. The decision variables are $x_i$ and $y_i$.

Two rectangles $1,2$ do not strictly overlap (i.e. they may overlap only by their edges) iff

$(x_2 + w_2 \leq x_1) \vee (x_1 + w_1 \leq x_2) \vee (y_1+h_1 \leq y_2) \vee (y_2+h_2 \leq y_1)$

How can I model this constraint using constraints suitable for a Linear Integer Program?

Auberon
  • 459

1 Answers1

1

$x_2 + w_2 \leq x_1 + Mz_1$

$x_1 + w_1 \leq x_2 + Mz_2$

$y_1 + h_1 \leq y_2 + Mz_3$

$y_2 + h_2 \leq y_1 + Mz_4$

$z_1 + z_2 + z_3 + z_4 \leq 3$

Where M is sufficiently large (i.e. the big M method). The $z_i$s are 0-1 variables.

Auberon
  • 459