# Shelved-Retrieved Method for Weakly Balanced Constrained Clustering Problems
## 3 Methodology
### Mathematical Formulation  
For a given point set \(X=\{\mathbf{x}_{1}=(x_{1}^{1},\ldots,x_{1}^{d}),\ldots,\mathbf{x}_{m}=(x_{m}^{1},\ldots,x _{m}^{d})\}\), each point is assigned a weight \(\omega_{j}=\omega(x_{j})>0\) from a weight set \(\Omega=\{\omega_{1},\ldots,\omega_{m}\}\) to represent its quantity information. This set is divided into \(n\) clusters, wherein the binary variable \(\xi_{i,j}\) indicates whether the point \(\mathbf{x}_{j}\in X\) belongs to cluster \(C_{i}\). For instance, \(\xi_{i,j}=1\) indicates that point \(\mathbf{x}_{j}\) belongs to cluster \(C_{i}\). Further, the weight of cluster \(C_{i}\) is determined by \(\omega(C_{i})=\sum_{j=1}^{m}\xi_{i,j}\omega_{j}\), which is required to satisfy the balancing constraint \(\omega(C_{i})\in[\kappa_{i}^{-},\kappa_{i}^{+}]\), wherein the minimal capacity \(\kappa_{i}^{-}>0\) and the maximal \(\kappa_{i}^{+}\) constitute the set \(K^{-}\) and \(K^{+}\), respectively.  
Except for the constraints on the cluster weights, the WBCC problem requires cluster connectivity. According to the cost kernel \(f\), a weight matrix is given in the datasets. Then, the corresponding graph \(G=(V,E)\) can be generated. The node set is defined as \(V=X\), and edges are added to the edge set \(E\) if the corresponding edge weight is finite in the weight matrix. Further, cluster \(C_{i}\) is connected if each induced subgraph \(G[C_{i}]\) is also connected.  
In this study, the WBCC problem uses the cost kernel \(f  
\[\kappa_{i}^{+}-\kappa_{i}^{-}>\max_{j=1,\ldots,m}\omega_{j}. \tag{3}\]  
Under Assumption 1, Model (1) has a feasible solution.  
Proof.: \(n=2\): Graph \(G\) can be divided into two connected sub-graphs, \(G_{1}\) and \(G_{2}\), where \(G_{1}=(V_{1},E_{1})\), \(G_{2}=(V_{2},E_{2})\).  
We assume \(\omega(V_{1})<\kappa_{1}^{-}\). We can select point \(\mathbf{x}_{t}\in V_{2}\), such that \(G[V_{1}+\mathbf{x}_{t}]\) and \(G[V_{2}-\mathbf{x}_{t}]\) is connected. Due to Equality (3), we can obtain  
\[\omega(V_{1}+\mathbf{x}_{t})=\omega(V_{1})+\omega_{t}\leq\kappa_{1}^{+}.\]  
If \(\omega(V_{1}+\mathbf{x}_{t})<\kappa_{1}^{-}\), we repeat the above operations. If \(\omega(V_{1}+\mathbf{x}_{t})\geq\kappa_{1}^{-}\), we prove this partition is a feasible solution. Due to Formula (2),  
\[\omega(V_{1})+\omega(V_{2})>\kappa_{1}^{-}+\kappa_{2}^{-}+(\kappa_{1}^{+}- \kappa_{1}^{-})+\omega_{t}=\kappa_{1}^{+}+\kappa_{2}^{-}+\omega_{t}>\kappa_{2 }^{-}+\omega(V_{1})+\omega_{t}.\]  
Then, \(\omega(V_{2})-\omega_{t}\geq\kappa_{2}^{-}\). Similarly, \(\omega(V_{2})-\omega_{t}\leq\kappa_{2}^{+}\).  
We assume that when \(n=k\), Model (1) has a feasible solution. When \(n=k+1\), we partition the point set into two clusters \(V_{1}\) and \(\hat{V}_{2}\) with \(\hat{\kappa}_{1}^{-}=\kappa_{1}^{-},\hat{\kappa}_{1}^{+}=\kappa_{1}^{+},\hat{ \kappa}_{2}^{+}=\sum_{i=2}^{k+1}\kappa_{i}^{-}\), \(\hat{\kappa}_{2}^{+}=\sum_{i=2}^{k+1}\kappa_{i}^{+}\). Then, we can obtain \(k+1\) clusters by partitioning the point set \(\hat{V}_{2}\).  
By induction, Model (1) has a feasible solution under Assumption 1 for all \(n\geq 2\).