- Given an \(n\times n\) square area,
- Partition this area into differently sized rectangles,
- 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}\] |
| 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:
- Initialization: \(P = \emptyset\).
- Solve model 1
- Record the solution \(y^*_k\), augment the set \(P\) and add this solution to \(Y^*_{p,k}\).
- Solve model 2
- If feasible: STOP. We have found the optimal solution.
- 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 |
References
- Mondriaan Tilings, https://yetanothermathprogrammingconsultant.blogspot.com/2020/04/mondriaan-tilings.html The problem and a mathematical model are detailed in this post.
