# The Color Mix Problem
## 1 Introduction  
The color mix problem (CMP; in this work we consider three colors) can be formulated as a particular case of the well-known problem--the quadratic assignment problem (QAP) [1]. The formulation is as follows. Given two integer quadratic matrices \(\mathbf{A}=\left(a_{ij}\right)_{n\times n^{\prime}}\mathbf{B}=\left(b_{ij} \right)_{n\times n^{\prime}}\), and a set \(\Pi_{n}\) of all possible permutations of the integers from \(0\) to \(n-1\), find a permutation \(p\in\Pi_{n}\) that minimizes the following function:  
\[z(p)=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_{ij}b_{p(i)p(j)}, \tag{1}\]  
where \(a_{ij}=1\) for \(i=0,\ \dots,\ m_{1}-1,j=m_{1},\ m_{1}+1,\dots,\ m-1,i=m_{1},m_{1}+1,\dots,\ m-1\), \(j=0,\ \dots,\ m_{1}-1\); \(a_{ij}=2\) for \(i,j=0,\ \dots,\ m_{1}-1,\ m_{1},m_{1}+1,\dots,\ m-1\), and \(a_{ij}=0\) otherwise (\(1\leq m_{1}<m,\ m_{1}<m<n\)) (see Figure 1). So, the objective can be transformed to finding the permutation elements \(p(0),\ \dots,\ p(m-1)\) (\(0\leq p(i)\leq n-1,i=0,\dots,\ m-1\)) such that the following simplified function is minimized:  
\[z(p)=\sum_{i=0}^{m_{1}-1}(2\sum_{j=0}^{m_{1}-1}b_{p(i)p(j)}+\sum_{j=m_{1}}^{m -1}b_{p(i)p(j)(j)})+\sum_{i=m_{1}}^{m-1}(\sum_{j=0}^{m_{1}-1}b_{p(i)p(j)}+2 \sum_{j=m_{1}}^{m-1}b_{p(i)p(j)}). \tag{2}\]  
The items in the matrix \(\mathbf{B}\) are symmetric distances between every pair of \(n\) elements. The distances are calculated by adopting the definition as in [2]:  
\[b_{kl}=b_{m_{2}+s,m_{2}+u}=\omega_{rstu},\ \omega_{rstu}=\max_{w_{1},u_{2} \in\{-1,0,1\}}\Bigg{\{}\frac{1}{\left(r-t+w_{1}n_{1}\right)^{2}+\left(s-u+w_{2 }n_{2}\right)^{2}}\Bigg{\}}, \tag{3}\]  
where \(k,l=0,\dots,\ n-1,r,t=0,\dots,n_{1}-1\,s,u=0,\dots,\ n_{2}-1\), \(n=n_{1}\times n_{2}\) (in our case, \(n_{1}=n_{2}\)). In other words, we have a grid (rectangle) of dimensions \(n_{1}\times n_{2}\) (for simplicity, \(n_{1}=n_{2}\)). More precisely, we have \(n=n_{1}\times n_{2}\) squares (dots, points) of identical size. For convenience, it may be recommended that \(n\) be equal to 2 raised to a power \(\lambda\), i.e., \(2^{\lambda}\) (for example, \(2^{6}\), \(2^{8}\), and so on). The squares are evenly positioned in \(n_{1}\) horizontal lines and \(n_{2}\) vertical columns. There are \(m_{1}\) squares of color \(color_{1}\) (say, red). Also, there are \(m_{2}=m-m_{1}\) squares of color \(color_{2}\) (for example, green) and also \(m_{3}=n-m=n-m_{1}-m_{2}\) squares of color \(color_{3}\) (say, blue). This forms a color mix pattern, i.e., a mixture (composition) of three colors (red, green, blue), which can be characterised by the parameters \(\frac{m_{1}}{n}\), \(\frac{m_{2}}{n}\), \(\frac{m_{3}}{n}\). Then, the aim is to obtain a configuration of all the points, i.e., a color pattern, where the colors (color squares) are distributed in the most uniform possible way. In other words, we are seeking to get fine, well-balanced color combinations; that is, we wish to obtain the most uniform possible pattern for each color (see Figure 2). It should be noted that the color mix problem is a more complex case of the grey pattern problem (GPP) [2], where one has \(n\) points in the rectangle and there are \(m\) black points, while the remaining points are white. The goal is to have a grey pattern where the black points are scattered as regularly as possible on the rectangle. The values of the elements of the analytical solution, i.e., permutation \(p\) are related to the corresponding coordinates (\(r\), \(s\)) of the sites (locations) on the grid through the following formulas: \(r=\frac{p(i)}{n_{2}}\), \(s=p(i)\) mod \(n_{2}\), \(i=0,\ \dots,\ n-1\). Note that the first \(m_{1}\) elements in the permutation determine the sites on the grid where the red squares are placed in. The next \(m_{2}\) elements define the positions of the green squares, and so on. Figure 1: Illustration of entries of matrix \(\mathbf{A}\) (\(n=16\), \(m=8\), \(m_{1}=3\)). Figure 2: Illustration of the (optimal) color mix pattern (\(n=64\), \(n_{1}=n_{2}=8\), \(m=8\), \(m_{1}=11\), \(m_{2}=12\), \(m_{3}=41\)).