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

See also

This problem is sourced from EvoCut [2].

Note

We add an implicit assumption \(N \ge 1\).

NP-hard: no

Description¶

Given an \(N \times 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 [2].

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2].

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 [2] (version: 1, name: EC1).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC1.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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\). This cut is invalid because the tile immediately to the left of a hole may span multiple rows and terminate on a different row.

\[ 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 [2] (version: 1, name: EC2).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC2.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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\). This cut is invalid because the tile immediately to the right of a hole may span multiple rows and start on a different row.

\[ 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 [2] (version: 1, name: EC3).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC3.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 \geq 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 [2] (version: 1, name: EC4).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC4.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 \geq 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 [2] (version: 1, name: EC5).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC5.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 [2] (version: 1, name: EC6).

Note

This is the IMO6 formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC6.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 [2] (version: 2, name: EC1).

Note

This is the IMO6 formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC1.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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 [2] (version: 2, name: EC2).

Note

This is the IMO6 formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC2.

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, \dots, N-1\}\)	\(R = \{0, 1, \dots, N-1\}\)
`C`	Set of column indices \(\{0, \dots, N-1\}\)	\(C = \{0, 1, \dots, N-1\}\)
`I`	Set of column interval pairs \((a, b)\) with \(a \leq 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} \]

Reformulations¶

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (invalid)¶

Note

Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → c (invalid)¶

Note

Formulation c has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → d (valid)¶

Note

Formulation d has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → e (valid)¶

Note

Formulation e has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → f (valid)¶

Note

Formulation f has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → g (valid)¶

Note

Formulation g has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → h (valid)¶

Note

Formulation h has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

a → i (valid)¶

Note

Formulation i has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`N`	\(N = N\)

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¶

Reformulations¶

a → b (invalid)¶

a → c (invalid)¶

a → d (valid)¶

a → e (valid)¶

a → f (valid)¶

a → g (valid)¶

a → h (valid)¶

a → i (valid)¶

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