Introduction
Piet Mondriaan (later Mondrian) (1872-1944) was a Dutch painter, famous for his abstract works [1].
A tiling problem is related to this [2]:
The problem can be stated as follows:
- Given is a square \((n \times n)\) area,
- Partition this square into multiple, integer-sided, non-congruent rectangles,
- Minimize the difference in size between the largest and the smallest rectangle.
Non-congruent means: only one \((p \times q)\) or \((q\times p)\) rectangle can be used.
It is interesting to make some predictions.
It is interesting to make some predictions.
- We try not to use a combination of very small and very large rectangles. That is obvious.
- Only using small rectangles will always lead to a larger difference, as we need many small rectangles to cover the complete square. This will lead automatically to a larger range of sizes.
- Very large rectangles are probably no good either: high probability we need some very small rectangles to fill up any remaining holes.
- So I guess, we will use medium-sized rectangles of similar size.
Example
Consider a small problem with \(n=5\). The possible sides for each rectangle are \(1,\dots,n\). From this, we can form a set of possible rectangles (I automated this step):
We see there are 14 different rectangles we can use. Note that the rectangle with size \((5 \times 5)\) is excluded. It would completely fill the area, while we need to place multiple rectangles. Also note: we only have \((p \times q)\) but not \((q \times p)\). We cannot use both such rectangles as they are congruent. We can rotate a rectangle when placing it.
An optimal solution for this problem is:
These are rectangles \(k5, k6, k12\) with \(k5\) being rotated. Obviously, this solution is not unique.
To model this, I use a binary variable: \[ x_{k,r,i,j} = \begin{cases} 1 & \text{if rectangle $k$ (rotated if $r=\mathrm{y}$) is placed at location $(i,j)$} \\ 0 & \text{otherwise}\end{cases}\] Here \(r = \{\mathrm{n},\mathrm{y}\}\) indicates if a rectangle is rotated. Note that not all rectangles can be rotated (it does not make sense to rotate a square, or there may not be space left to rotate for a given position).
For convenience, I also introduce \[y_{k} = \begin{cases} 1 & \text{if rectangle $k$ is used} \\ 0 & \text{otherwise}\end{cases}\] This is essentially an aggration of \(x\).
In addition, I use a few more complex data structures: \[\mathit{ok}_{k,r,i,j} = \begin{cases} \mathit{Yes} & \text{if we can place rectangle $k$ at location $(i,j)$} \\ \mathit{No} & \text{otherwise}\end{cases}\] Again, \(r\) indicates if rectangle \(k\) is rotated. I implemented this as a GAMS set. You can consider it as a Boolean data structure. Furthermore: \[\mathit{cover}_{k,r,i,j,i',j'} = \begin{cases} \mathit{Yes} & \text{if cell $(i',j')$ is covered by placing rectangle $k$ at location $(i,j)$} \\ \mathit{No} & \text{otherwise}\end{cases}\]
These sets are large. The set ok looks like:
The set cover is even larger:
The reason to develop these sets is to make the equations simpler. In addition, we can develop, test and debug the calculation of these sets in isolation of the test of the model and before the equations are written.
With this, we can formulate:
When solving this model, we see:
---- 65 SET s sizes of rectangles (height or width) s1, s2, s3, s4, s5 ---- 65 SET k rectangle id k1 , k2 , k3 , k4 , k5 , k6 , k7 , k8 , k9 , k10, k11, k12, k13, k14 ---- 65 SET rec rectangles s1 s2 s3 s4 k1 .s1 YES k2 .s2 YES k3 .s2 YES k4 .s3 YES k5 .s3 YES k6 .s3 YES k7 .s4 YES k8 .s4 YES k9 .s4 YES k10.s4 YES k11.s5 YES k12.s5 YES k13.s5 YES k14.s5 YES
We see there are 14 different rectangles we can use. Note that the rectangle with size \((5 \times 5)\) is excluded. It would completely fill the area, while we need to place multiple rectangles. Also note: we only have \((p \times q)\) but not \((q \times p)\). We cannot use both such rectangles as they are congruent. We can rotate a rectangle when placing it.
Optimal solution
An optimal solution for this problem is:
These are rectangles \(k5, k6, k12\) with \(k5\) being rotated. Obviously, this solution is not unique.
Optimization model
To model this, I use a binary variable: \[ x_{k,r,i,j} = \begin{cases} 1 & \text{if rectangle $k$ (rotated if $r=\mathrm{y}$) is placed at location $(i,j)$} \\ 0 & \text{otherwise}\end{cases}\] Here \(r = \{\mathrm{n},\mathrm{y}\}\) indicates if a rectangle is rotated. Note that not all rectangles can be rotated (it does not make sense to rotate a square, or there may not be space left to rotate for a given position).
For convenience, I also introduce \[y_{k} = \begin{cases} 1 & \text{if rectangle $k$ is used} \\ 0 & \text{otherwise}\end{cases}\] This is essentially an aggration of \(x\).
In addition, I use a few more complex data structures: \[\mathit{ok}_{k,r,i,j} = \begin{cases} \mathit{Yes} & \text{if we can place rectangle $k$ at location $(i,j)$} \\ \mathit{No} & \text{otherwise}\end{cases}\] Again, \(r\) indicates if rectangle \(k\) is rotated. I implemented this as a GAMS set. You can consider it as a Boolean data structure. Furthermore: \[\mathit{cover}_{k,r,i,j,i',j'} = \begin{cases} \mathit{Yes} & \text{if cell $(i',j')$ is covered by placing rectangle $k$ at location $(i,j)$} \\ \mathit{No} & \text{otherwise}\end{cases}\]
These sets are large. The set ok looks like:
---- 103 SET ok usable position INDEX 1 = k1 j1 j2 j3 j4 j5 n.i1 YES YES YES YES YES n.i2 YES YES YES YES YES n.i3 YES YES YES YES YES n.i4 YES YES YES YES YES n.i5 YES YES YES YES YES INDEX 1 = k2 j1 j2 j3 j4 j5 n.i1 YES YES YES YES YES n.i2 YES YES YES YES YES n.i3 YES YES YES YES YES n.i4 YES YES YES YES YES y.i1 YES YES YES YES y.i2 YES YES YES YES y.i3 YES YES YES YES y.i4 YES YES YES YES y.i5 YES YES YES YES ... INDEX 1 = k13 j1 j2 j3 n.i1 YES YES YES y.i1 YES y.i2 YES y.i3 YES INDEX 1 = k14 j1 j2 n.i1 YES YES y.i1 YES y.i2 YES
The set cover is even larger:
---- 103 SET cover coverage of cells INDEX 1 = k1 INDEX 2 = n INDEX 3 = i1 INDEX 4 = j1 j1 i1 YES INDEX 1 = k1 INDEX 2 = n INDEX 3 = i1 INDEX 4 = j2 j2 i1 YES ... INDEX 1 = k14 INDEX 2 = y INDEX 3 = i1 INDEX 4 = j1 j1 j2 j3 j4 j5 i1 YES YES YES YES YES i2 YES YES YES YES YES i3 YES YES YES YES YES i4 YES YES YES YES YES INDEX 1 = k14 INDEX 2 = y INDEX 3 = i2 INDEX 4 = j1 j1 j2 j3 j4 j5 i2 YES YES YES YES YES i3 YES YES YES YES YES i4 YES YES YES YES YES i5 YES YES YES YES YES
The reason to develop these sets is to make the equations simpler. In addition, we can develop, test and debug the calculation of these sets in isolation of the test of the model and before the equations are written.
With this, we can formulate:
| 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}\] |
When solving this model, we see:
---- 146 VARIABLE x.L place tile j1 j4 k5 .y.i4 1 k6 .n.i1 1 k12.n.i1 1 ---- 149 VARIABLE y.L tile is used k5 1, k6 1, k12 1 ---- 157 PARAMETER v tile numbers j1 j2 j3 j4 j5 i1 6 6 6 12 12 i2 6 6 6 12 12 i3 6 6 6 12 12 i4 5 5 5 12 12 i5 5 5 5 12 12 ---- 159 VARIABLE smallest.L = 6.000 smallest used tile VARIABLE largest.L = 10.000 largest used tile VARIABLE z.L = 4.000 objective
It is noted that these types of formulations lead to very large models [5].
One remaining question is whether we can use some symmetry-breaking constraint to speed up solution times.
A larger problem
It looks like \(n=19\) is interesting [3]. This is about the limit that we can solve comfortably (a few hours to global optimality) with a MIP solver. This model had about 36,000 binary variables.
 |
| An optimal 19x19 problem |
The colors are not part of the model: they were added by hand to make the picture more Mondrianic.
A list of optimal objective values can be found in [4].
References
- Piet Mondrian, https://en.wikipedia.org/wiki/Piet_Mondrian
- Mondrian Puzzle -- Numberphile, https://www.youtube.com/watch?v=49KvZrioFB0
- Brady Haran, Mondrian Art Puzzle, https://www.bradyharanblog.com/blog/mondrian-art-puzzle
- A276523 in The Online Encyclopedia of Sequences, https://oeis.org/A276523
- Tiling, https://yetanothermathprogrammingconsultant.blogspot.com/2020/03/tiling.html This post shows a comparison of the above formulation with a "no-overlap" formulation for a related problem.
- Mondriaan Tilings 2, http://yetanothermathprogrammingconsultant.blogspot.com/2020/04/mondriaan-tilings-2.html. This post demonstrates an alternative approach to this problem.
No comments:
Post a Comment