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

See also

This problem is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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)¶

See also

This formulation is sourced from EvoCut (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} \]

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

Description¶

Formulations¶

Formulation a (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation b (invalid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation c (invalid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation d (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation e (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation f (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation g (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation h (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation i (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation `a` (valid)¶

Formulation `b` (invalid)¶

Formulation `c` (invalid)¶

Formulation `d` (valid)¶

Formulation `e` (valid)¶

Formulation `f` (valid)¶

Formulation `g` (valid)¶

Formulation `h` (valid)¶

Formulation `i` (valid)¶