## 2 Item Assignment Model  
The purpose of item assignment is to determine the most effective in-store locations of items to maximize the possibility of cross-selling. In practice, item assignment based on association rule mining starts by grouping sub-items; that is, sub-items are classified into different categories. Grouping sub-items allows the association information to remain useful, even if some sub-items are discontinued. Usually, the group information of sub-items is predetermined; e.g., diapers and pacifiers are to be grouped as \"baby\" items. The strengths of the associations are measured across these grouped items. We apply _lift_, a measure of association, to represent the possibility of cross-selling. Let \(X\) and \(Y\) be sets of items. Assuming that \(Pr(X)\) is the probability of containing \(X\) in a transaction database and \(Pr(Y\,|\,X)\) is the conditional probability of including \(Y\) together when a transaction contained \(X\), _lift_ (\(X\to Y\)) is defined as shown in Equation (1):  
\[lift(X\to Y)=Pr(Y|X)/Pr(Y)=\frac{Pr(X\cap Y)}{Pr(X)Pr(Y)}. \tag{1}\]  
_Lift_ (\(X\to Y\)) measures how much the possibility of purchasing \(Y\) increases after buying \(X\) rather than buying \(Y\) alone. If _lift_ (\(X\to Y\)) is greater than 1, then \(X\) and \(Y\), positively correlated, can be placed together for cross-selling. Let us assume that \(n\) items are to be located at \(n\) sites, with one item at each site. Let \(I=\{I_{1},\,I_{2},\,\ldots,\,I_{n}\}\) be the set of items and \(S=\{S_{1},\,S_{2},\,\ldots,\,S_{n}\}\) be the set of sites. Suppose that \(x_{ij}\) is 1 (one) if item \(I_{i}\) is located at site \(S_{j}\) and 0 (zero) otherwise, and \(y_{ij}\) is 1 if site \(S_{i}\) is adjacent to \(S_{j}\) and 0 otherwise. For a given layout, \(y_{ij}\) is given, and \(x_{ij}\) is a decision variable. The item assignment model can be stated as shown in Equation (2):  
\[ \begin{array}{ll}\text{Maximize}&\sum_{i\
eq j,k\
eq l}\,lift\,\big{(}I_{i }\to I_{j}\big{)}\times x_{ik}\times x_{jl}\times y_{kl}\\ \text{Subject to}&\sum_{i=1}^{n}x_{ik}=1,k\,\,=\,\,1,\,\ldots,\,n,\\ &\sum_{k=1}^{n}x_{ik}=1,i\,\,=\,\,1,\,\ldots,\,n,\\ &x_{ik}=\left\{\begin{array}{ll}1,&if\,\,item\,\,I_{i}\,\,is\,\,located\,\,at\, site\,S_{k}\\ 0,&otherwise.\end{array}\right.\end{array}  \tag{2}\]  
The objective function in Equation (2) represents the sum of possibilities of cross-selling for a given assignment. Each item must be located at one site by the constraint \(\sum_{k=1}^{n}x_{ik}=1\). Likewise, each site must hold only one item by the constraint \(\sum_{i=1}^{n}x_{ik}=1\). According to \(y_{kl}\) in the objective function, the possibility of cross-selling is added to the objective value only if the two items are placed at sites near one another. For example, suppose that six items are assigned to six sites and the lifts of two items are given in Table 1. Lift has the characteristic that it is symmetric: _lift_ (\(X\to Y\)) = _lift_ (\(Y\to X\)). Therefore, we give lifts of items in the form of a triangular matrix, as illustrated in Table 1.  
Let us assume that the layout of the six sites and an item assignment are as shown in Figure 1a,b, respectively. Let us denote Figure 1b as BASE_ASSIGN. Then, the total possibility of cross-selling can be calculated as follows. Item C is placed near item B and item E, and _lift_ (C \(\to\) B) and _lift_ (C \(\to\) E) are added to the total possibility of cross-selling, i.e., \(1.1+1.5\). Likewise, the seven lifts of items placed in close proximity are added to the total possibility of cross-selling. As a result, the total possibility of cross-selling is \(1.1+1.3\) + \(0+1.3+1.5+1.6+1.3=8.1\). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & **A** & **B** & **C** & **D** & **E** & **F** \\ \hline A & - & 1.6 & 0 & 1.3 & 0 & 1.2 \\ B & 1.6 & - & 1.1 & 1.4 & 0 & 1.3 \\ C & 0 & 1.1 & - & 1.3 & 1.5 & 0 \\ D & 1.3 & 1.4 & 1.3 & - & 0 & 1.3 \\ E & 0 & 0 & 1.5 & 0 & - & 1.3 \\ F & 1.2 & 1.3 & 0 & 1.3 & 1.3 & - \\ \hline \hline \end{tabular}
\end{table}