---
tocdepth: 3
---

# p7 | Rectangular Tiling with One Hole per Row and Column (IMO6)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- We add an implicit assumption $N \ge 1$.
- EvoCut arXiv submission `v1` proposes a family of six inequalities used to generate formulations `p7.b-g`.
- EvoCut arXiv submission `v2` proposes two inequalities used to generate formulations `p7.h-i`.
```


## Description

Given an N x N grid of unit squares, place axis-aligned rectangular tiles (no overlaps) so that each row and each column contains exactly one uncovered unit square (a hole); the objective is to minimize the number of tiles used

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- This is the MILP formulation given in Appendix F.5 of EvoCut arXiv submission `v1`.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `b` (invalid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC1).
```

```{note}
- A hole at $(i,j)$ forces an interval ending at column $j-1$ to terminate on row $i$.
- This cut was identified by `FLARE` to be invalid. The tile immediately to the left of a hole may span multiple rows and thus terminate on different row.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Horizontal-Left Break (V1 EC1): a hole at (i,j) forces an interval ending at column j-1 to terminate at row i.

  $$ h_{ij} \le \sum_{(a,b) \in I:\, b=j-1} t_i^{ab} \quad \forall i \in \{0,\dots,N-1\},\; \forall j \in \{1,\dots,N-1\} $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `c` (invalid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC2).
```

```{note}
- A hole at $(i, j)$ forces any tile interval starting at column $j+1$ to begin on row $i$.
- This cut was identified by `FLARE` to be invalid. The tile immediately to the right of a hole may span multiple rows and thus start on different row.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Horizontal-Right Break (V1 EC2): a hole at (i,j) forces an interval starting at column j+1 to begin at row i.

  $$ h_{ij} \le \sum_{(a,b) \in I:\, a=j+1} s_i^{ab} \quad \forall i \in \{0,\dots,N-1\},\; \forall j \in \{0,\dots,N-2\} $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `d` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC3).
```

```{note}
- A hole in the top row at column $j$ forces a new strip covering column $j$ to begin in row $1$, breaking the column at the hole vertically.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Top-Row Vertical Break (V1 EC3): a hole in row 0 forces a strip starting in row 1 to cover the same column (only when N >= 2).

  $$ h_{0,j} \le \sum_{(a,b) \in I:\, a \le j \le b} s_1^{ab} \quad \forall j \in \{0,\dots,N-1\},\; N \ge 2 $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `e` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC4).
```

```{note}
- A hole in the bottom row at column $j$ forces a strip covering column $j$ to terminate in row $N-2$, breaking the column at the hole vertically.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Bottom-Row Vertical Break (V1 EC4): a hole in row N-1 forces a strip ending in row N-2 to cover the same column (only when N >= 2).

  $$ h_{N-1,j} \le \sum_{(a,b) \in I:\, a \le j \le b} t_{N-2}^{ab} \quad \forall j \in \{0,\dots,N-1\},\; N \ge 2 $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `f` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC5).
```

```{note}
- An interior hole at $(i, j)$ forces a strip covering column $j$ to terminate in row $i-1$, breaking the column at the hole from above.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Interior Vertical-Above Break (V1 EC5): an interior hole at (i,j) forces a strip ending in row i-1 to cover the same column.

  $$ h_{ij} \le \sum_{(a,b) \in I:\, a \le j \le b} t_{i-1}^{ab} \quad \forall i \in \{1,\dots,N-2\},\; \forall j \in \{0,\dots,N-1\} $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `g` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC6).
```

```{note}
- An interior hole at $(i, j)$ forces a strip covering column $j$ to begin in row $i+1$, breaking the column at the hole from below.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Interior Vertical-Below Break (V1 EC6): an interior hole at (i,j) forces a strip starting in row i+1 to cover the same column.

  $$ h_{ij} \le \sum_{(a,b) \in I:\, a \le j \le b} s_{i+1}^{ab} \quad \forall i \in \{1,\dots,N-2\},\; \forall j \in \{0,\dots,N-1\} $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `h` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC1).
```

```{note}
- If the hole vacates column $j$ between rows $i-1$ and $i$ (i.e., the hole is at column $j$ in row $i-1$ but not in row $i$), then column $j$ must be covered by a strip that begins at row $i$.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Vacated Column (V2 EC1): if the hole vacates column j between rows i-1 and i, then column j must be covered by a strip starting at row i.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} s_i^{ab} \ge h_{i-1,j} - h_{ij} \quad \forall i \in \{1,\dots,N-1\},\; \forall j \in \{0,\dots,N-1\} $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$

### Formulation `i` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC2).
```

```{note}
- If two columns $j$ and $k$ are jointly covered by a single tile in row $i-1$ and the hole sits at column $k$ in row $i$, then column $j$ must be covered by a new strip starting in row $i$.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `N` | Size of the grid (number of rows and columns) | integer | *scalar* |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `R` | Set of row indices {0, ..., N-1} | $R = \{0, 1, \dots, N-1\}$ |
| `C` | Set of column indices {0, ..., N-1} | $C = \{0, 1, \dots, N-1\}$ |
| `I` | Set of column interval pairs (a, b) with a <= b | $I = \{(a, b) \in C \times C : a \le b\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `h` | 1 if (i,j) is the unique hole in row i and column j, 0 otherwise | binary | `[N, N]` |
| `x` | 1 if row i, columns a through b are covered by the same tile, 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `s` | 1 if a tile starts at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |
| `t` | 1 if a tile ends at row i for column interval (a,b), 0 otherwise | binary | `(i, a, b) for i in R for (a, b) in I` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Grid size is positive. | $N \ge 1$ | yes |


#### Constraints

- Each row contains exactly one hole.

  $$ \sum_{j=0}^{N-1} h_{ij} = 1 \quad \forall i \in \{0,\dots,N-1\} $$

- Each column contains exactly one hole.

  $$ \sum_{i=0}^{N-1} h_{ij} = 1 \quad \forall j \in \{0,\dots,N-1\} $$

- Each cell is either a hole or covered by exactly one tile interval.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} x_i^{ab} + h_{ij} = 1 \quad \forall i,j \in \{0,\dots,N-1\} $$

- Top-row flow: a tile covering interval (a,b) in row 0 must start there.

  $$ x_0^{ab} - s_0^{ab} = 0 \quad \forall (a,b) \in I $$

- Mid-row flow: tile coverage at row i equals coverage from previous row plus new starts minus ends.

  $$ x_i^{ab} - x_{i-1}^{ab} - s_i^{ab} + t_{i-1}^{ab} = 0 \quad \forall i \in \{1,\dots,N-1\},\; \forall (a,b) \in I $$

- Bottom-row flow: a tile covering interval (a,b) in the last row must end there.

  $$ x_{N-1}^{ab} - t_{N-1}^{ab} = 0 \quad \forall (a,b) \in I $$

- Broken Interval (V2 EC2): if columns j and k shared a tile in row i-1 and the hole is at k in row i, then column j must be covered by a new start in row i.

  $$ \sum_{(a,b) \in I:\, a \le j \le b} s_i^{ab} \ge \sum_{(a,b) \in I:\, a \le \min(j,k),\, b \ge \max(j,k)} x_{i-1}^{ab} + h_{ik} - 1 \quad \forall i \in \{1,\dots,N-1\},\; \forall j,k \in \{0,\dots,N-1\},\; j \neq k $$

#### Objective

Minimize the total number of rectangular tiles used.

$$ \min \sum_{i=0}^{N-1} \sum_{(a,b) \in I} s_i^{ab} $$