Filling rectangles with polyominos

I know about dominos, but polyominos [1] are new for me. In [2] a problem is posted: fill a rectangle (or square) with a number of different polyominos. No overlap or rotation allowed. I assume there is no limitation in the supply of polyominos.

For example, consider a $11 \times 11$ grid, and choose from the following building blocks:

Five different polyominos

We can try to fill our grid, but we will not always succeed:

Fail to cover complete grid

I solved this as a MIP as follows. My decision variables are:

$$x_{i,j,k} = \begin{cases} 1 & \text{if we place polyomino $k$  at location $(i,j)$}\\ 0 & \text{otherwise} \end{cases}$$

I used as rule that the left-upper corner of each polynomino is its anchor. I.e. in the picture above we have $x_{1,1,4} = 1$, $x_{2,1,2}=1$, $x_{1,3,5}=1$ etc.

To formulate a non-overlap constraint I populated a set $cover_{i,j,k,i',j'}$, with elements that exist  if cell $(i',j')$ is covered when we place polyomino $k$ in cell $(i,j)$. To require each cell $(i',j')$ is covered we can say:

$$\forall i',j':  \sum_{i,j,k|cover_{i,j,k,i',j'}} x_{i,j,k} = 1$$

This constraint is infeasible if we cannot cover each cell $(i',j')$ exactly once. In order to make sure we can show a meaningful solution when we cannot cover each cell, we formulate the following optimization model:

$$\begin{align} \max\>&\sum_{i,j} y_{i,j}\\&y_{i',j'} = \sum_{i,j,k|cover_{i,j,k,i',j'}} x_{i,j,k}\\&x_{i,j,k}\in \{0,1\}\\&y_{i,j} \in \{0,1\}\end{align}$$

Here $y_{i,j}=1$ indicates cell $(i,j)$ is covered exactly once, and $y_{i,j}=0$ says the cell is not covered.

With a little bit of effort we can produce the following:

61 x 61 board with 9 different polyominos

A SAT solver may be better suited for this [2], but MIP works for all but very large instances.

References

1. Polyomino, https://en.wikipedia.org/wiki/Polyomino
2. 2D bin packing on a grid, https://stackoverflow.com/questions/47918792/2d-bin-packing-on-a-grid