Wednesday, April 1, 2020

Mondriaan Tilings


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.

  • 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. 


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

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


i1         YES

INDEX 1 = k1  INDEX 2 = n  INDEX 3 = i1  INDEX 4 = 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].


  1. Piet Mondrian, 
  2. Mondrian Puzzle -- Numberphile,
  3. Brady Haran, Mondrian Art Puzzle
  4. A276523 in The Online Encyclopedia of Sequences
  5. Tiling, This post shows a comparison of the above formulation with a "no-overlap" formulation for a related problem.
  6. Mondriaan Tilings 2, This post demonstrates an alternative approach to this problem.

No comments:

Post a Comment