Mondriaan Tilings 2

In [1], I showed a Mixed Integer Programming formulation for the Mondriaan Tiling Problem. To summarize, the problem can be stated as:

1. Given an $n\times n$ square area,
2. Partition this area into differently sized rectangles,
3. Such that the difference in size between the largest and the smallest rectangle is minimized.

Instead of partitioning, we can look at the problem as a tiling problem: given a set of differently sized tiles, place a subset of them on the area such that the whole area is covered and the difference in the size of used tiles (largest minus smallest) is minimized.

The model in [1] looked like:

Original MIP Model

$$\begin{align}\min\> & \color{darkred}u - \color{darkred}\ell\\ & \sum_{k,r,i,j|\color{darkblue}{\mathit{cover}}(k,r,i,j,i',j')}\color{darkred}x_{k,r,i',j'}=1 && \forall i',j'&&\text{cover cell $(i',j')$}\\ &\color{darkred}y_k = \sum_{r,i,j|\color{darkblue}{\mathit{ok}}(k,r,i,j)}\color{darkred}x_{k,r,i,j}&& \forall k && \text{select max one type of rectangle} \\ & \color{darkred}\ell \le \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k + \color{darkblue}M (1-\color{darkred}y_k) && \forall k && \text{bound smallest area}\\ & \color{darkred}u \ge \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k  && \forall k && \text{bound largest area}\\ & \sum_k \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k = \color{darkblue} n^2 && && \text{extra constraint}\\ & \color{darkred}x_{k,r,i,j} \in \{0,1\} \\&  \color{darkred}y_k \in \{0,1\} \\ & \color{darkred}u, \color{darkred}\ell \ge 0 \\& \color{darkblue}M = \max_k \color{darkblue}{\mathit{area}}_k\end{align}$$

The main (binary) variables are:

Decision Variables
$$\color{darkred} y_k = \begin{cases} 1 & \text{if tile $k$ is selected} \\ 0 & \text{otherwise} \end{cases}$$
$$\color{darkred} x_{k,r,i,j} = \begin{cases} 1 & \text{if tile $k$ (orientation $r$) is placed at location $(i,j)$} \\ 0 & \text{otherwise} \end{cases}$$

Here I want to discuss a different approach. Instead of solving the problem in one swoop for both $y$ (select tiles) and $x$ (place tiles), we can design a simple algorithm that iterates between two different models until we find a feasible integer solution. By ordering things from best to worse, as soon as we find a feasible solution, we have the optimal solution.

The first model is dedicated to select $y$ variables (i.e. select tiles) such that $$\sum_k \mathit{area}_k \cdot y_k = n^2$$ and where the objective $$\min \> u-\ell$$ is optimized. The second model takes a solution for $y$ and checks if it is feasible. If not feasible, we go back to model 1 and generate a new, next best solution for $y$.

Model 1: selection of tiles, can look like:

MIP Model 1: Generate proposals for $y$

$$\begin{align}\min\> & \color{darkred}u - \color{darkred}\ell\\ & \color{darkred}\ell \le \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k + \color{darkblue}M (1-\color{darkred}y_k) && \forall k && \text{bound smallest area}\\ & \color{darkred}u \ge \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k  && \forall k && \text{bound largest area}\\ & \sum_k \color{darkblue}{\mathit{area}}_k \cdot\color{darkred}y_k = \color{darkblue} n^2 && && \text{area constraint}\\ & \sum_k (2 \color{darkblue}Y^*_{p,k} -1) \color{darkred}y_k \le \sum_k \color{darkblue}Y^*_{p,k}-1 && p \in P && \text{cut off previously found solutions} \\ &  \color{darkred}y_k \in \{0,1\} \\ & \color{darkred}u, \color{darkred}\ell \ge 0 \\& \color{darkblue}M = \max_k \color{darkblue}{\mathit{area}}_k\end{align}$$

Previously found solutions for $y$ are stored in the data structure $Y^*$. The cut will forbid any previously found solution to be considered again. In the first solve, we can use $P=\emptyset$ (no previously found solutions).

The second model establishes whether the solution $y^*$ in model 1 is feasible. This model, given a selection of tiles ($y^*$) will try to place the tiles such that all locations of the whole area are covered by exactly one tile.

MIP Model 2: Check feasibility of $y^*$

$$\begin{align}\min\> & 0 \\ & \sum_{k^*,r,i,j|\color{darkblue}{\mathit{cover}}(k^*,r,i,j,i',j')}\color{darkred}x_{k^*,r,i',j'}=1 && \forall i',j' \text{ and } k^* \in \color{darkblue} K^* &&\text{cover cell $(i',j')$}\\ &\sum_{r,i,j|\color{darkblue}{\mathit{ok}}(k^*,r,i,j)}\color{darkred}x_{k^*,r,i,j} = 1&& \text{where } k^* \in \color{darkblue} K^* && \text{select one type of rectangle}\\ & \color{darkred}x_{k^*,r,i,j} \in \{0,1\}  \\ & \color{darkblue} K^* = \{k|\color{darkblue}y_k^*=1\} && &&\text{set of selected tiles}\end{align}$$

The algorithm can look like:

1. Initialization: $P = \emptyset$.
2. Solve model 1
3. Record the solution $y^*_k$, augment the set $P$ and add this solution to $Y^*_{p,k}$.
4. Solve model 2
5. If feasible: STOP. We have found the optimal solution.
6. Go to step 2.

Small example

When we solve a $10\times 10$ problem, we need 10 cycles:

----    227 PARAMETER ysolrep  solutions for m1 (ordered by obj)

              obj    smallest     largest      status

sol1            3          24          27  Infeasible
sol2            6          18          24  Infeasible
sol3            6          18          24  Infeasible
sol4            7           9          16  Infeasible
sol5            7           9          16  Infeasible
sol6            7          21          28  Infeasible
sol7            7          21          28  Infeasible
sol8            7          14          21  Infeasible
sol9            7          14          21  Infeasible
sol10           8           4          12    Feasible

The status column indicates what model 2 thinks about this proposal. The first 9 generated proposals were infeasible. The first tiling with a difference of 8 was feasible, and we can declare that an optimal solution. We have proven that no better solution exists.

The results look like:

Solution for 10x10 problem

Large example

The results for a $25\times 25$ problem are:

Optimal solution for 25x25 problem

This problem required 246 cycles (i.e. 496 models to be solved).

References

1. Mondriaan Tilings, https://yetanothermathprogrammingconsultant.blogspot.com/2020/04/mondriaan-tilings.html The problem and a mathematical model are detailed in this post.