# The Color Mix Problem
## 2 Preliminaries  
Suppose that \(p(v)\) (\(v=0,\ \dots,\ n-1\)) and \(p(w)\) (\(w=0,\ \dots,\ n-1\), \(v\
eq w\)) are two elements in the permutation \(p\). Then \(p^{v,w}\) is defined in the following way:  
\[p^{v,w}(i)=\left\{ \begin{array}{ll}p(i),&i\
eq v,w\\ p(v),&i=w\\ p(w),&i=v\end{array} \right. ;\ i=0,\ \dots,\ n-1. \tag{4}\]  
A neighbourhood function \(\Theta\): \(\Pi_{n}\to 2^{\Pi_{n}}\) assigns for each \(p\in\Pi_{n}\) a set of neighbouring solutions \(\Theta(p)\subseteq\Pi_{n}\). In particular, the 1-exchange neighbourhood function \(\Theta_{1}\) is defined as follows:  
\[\Theta_{1}(p)=\big{\{}p^{\prime}:p^{\prime}\in\Pi_{n},\big{(}\delta_{1}\big{(} p,p^{\prime}\big{)}=1\ \vee\ \delta_{2}\big{(}p,p^{\prime}\big{)}=1\big{)}\ \wedge\ \delta_{3}\big{(}p,p^{\prime}\big{)}\leq 1 \big{\}}, \tag{5}\]where \(p\in\Pi_{n}\) and \(\delta_{1}(p,\ p^{\prime})\), \(\delta_{2}(p,\ p^{\prime})\), \(\delta_{3}(p,\ p^{\prime})\) denote the corresponding distance measures between the solutions \(p\) and \(p^{\prime}\). The distances \(\delta_{1}\), \(\delta_{2}\), \(\delta_{3}\) between two solutions \(p\) and \(p^{\prime}\) can be defined according to the following formulas:  
\[\delta_{1}\big{(}p,p^{\prime}\big{)}=m_{1}-\big{|}\{p(i):i=0,\ldots,m_{1}-1\} \cap\big{\{}p^{\prime}(i):i=0,\ldots,m_{1}-1\big{\}}\big{|}, \tag{6}\]  
\[\delta_{2}\big{(}p,p^{\prime}\big{)}=m_{2}-\big{|}\{p(i):i=m_{1},\ldots,m-1\} \cap\big{\{}p^{\prime}(i):i=m_{1},\ldots,m-1\big{\}}\big{|}, \tag{7}\]  
\[\delta_{3}\big{(}p,p^{\prime}\big{)}=m-\big{|}\{p(i):i=0,\ldots,m-1\}\cap\big{\{} p^{\prime}(i):i=0,\ldots,m-1\}\big{|}, \tag{8}\]  
where \(m_{2}=m-m_{1}\). The solution \(p^{v,w}\) can simply be obtained from the existing solution \(p\) by accomplishing the pairwise interchange move \(\phi(p,v,w)\): \(\Pi_{n}\times N\times N\rightarrow\Pi_{n}\), which swaps the \(v\)th and \(w\)th elements in the given solution. Thus, \(p^{v,w}=\phi(p,v,w)\). For the neighbouring solutions \(p\) and \(p^{v,w}\), the difference in the values of the objective function is calculated in \(O(1)\) time by using the following formula:  
\[\Delta_{z}(p^{v,w},p)=z(p^{v,w})-z(p)=\left\{ \begin{array}{ll}2\big{(}c_{1}( p(w))-c_{1}(p(v))-2b_{p(v)p(w)}\big{)},&v\in\{0,\ldots,m_{1}-1\},w\in\{m, \ldots,n-1\}\\ 2\big{(}c_{2}(p(w))-c_{2}(p(v))-2b_{p(v)p(w)}\big{)},&v\in\{m_{1},\ldots,m-1\},w\in\{m,\ldots,n-1\}\\ 2\big{(}c_{3}(p(w))-c_{3}(p(v))-2b_{p(v)p(w)}\big{)},&v\in\{0,\ldots,m_{1}-1\},w\in\{m_{1},\ldots,m-1\}\end{array} \right., \tag{9}\]  
\[\text{where }c_{1}(x),\,c_{2}(x),\,c_{3}(x)\text{ are contributions of the element }x\text{ (the sum of related distances):}\]  
\[c_{1}(x)=2\sum_{y=0}^{m_{1}-1}b_{x,p(y)}+\sum_{y=m_{1}}^{m-1}b_{x,p(y)},x=0, \ldots n-1, \tag{10}\]  
\[c_{2}(x)=\sum_{y=0}^{m_{1}-1}b_{x,p(y)}+2\sum_{y=m_{1}}^{m-1}b_{x,p(y)},x=0, \ldots,\ n-1, \tag{11}\]  
\[c_{3}(x)=\sum_{y=0}^{m_{1}-1}b_{x,p(y)}-\sum_{y=m_{1}}^{m-1}b_{x,p(y)},x=0, \ldots,n-1. \tag{12}\]  
Note that, after the exchange of the permutation elements \(p(v)\) and \(p(w)\), the contributions must be updated according to these equations:  
\[c_{1}(x)=\left\{ \begin{array}{ll}c_{1}(x)+2\Big{(}b_{x,p(v)}-b_{x,p(w)} \Big{)},&v\in\{0,\ldots,m_{1}-1\},w\in\{m,\ldots,n-1\}\\ c_{1}(x)+\Big{(}b_{x,p(v)}-b_{x,p(w)}\Big{)},&v\in\{m_{1},\ldots,m-1\},w\in\{m,\ldots,n-1\}\\ c_{1}(x)+\Big{(}b_{x,p(v)}-b_{x,p(w)}\Big{)},&v\in\{0,\ldots,m_{1}-1\},w\in \{m_{1},\ldots,m-1\}\end{array} \right.,x=0,\ldots,\ n-1, \tag{13}\]  
\[c_{2}(x)=\left\{ \begin{array}{ll}c_{2}(x)+\Big{(}b_{x,p(v)}-b_{x,p(w)} \Big{)},&v\in\{0,\ldots,m_{1}-1\},w\in\{m,\ldots,n-1\}\\ c_{2}(x)+2\Big{(}b_{x,p(v)}-b_{x,p(w)}\Big{)},&v\in\{m_{1},\ldots,m-1\},&w\in \{m,\ldots,n-1\}\\ c_{2}(x)-\Big{(}b_{x,p(v)}-b_{x,p(w)}\Big{)},&v\in\{0,\ldots,m_{1}-1\},w\in \{m_{1},\ldots,m-1\}\end{array} \right.,x=0,\ldots,\ n-1, \tag{14}\]  
\[c_{3}(x)=\left\{