Original question:
Given a symmetric matrix with matches count between different transcriptions, the objective is to maximize the batches total matches count while minimize the standard deviation between the batch match counts where each batch allows a fixed number S of unique transcriptions and the number of batches is equal to the number of transcriptions divided by the fixed size S. Is there any way to relax this Knapsack problem to have at least high enough matches in every batch?
Updated question:
Let $S$ a symmetric matrix with size $N_s$ (+ 1 given the matrix labels) with matches count between different transcriptions, where $S[T1, T3]$ - 5 are the number of matches between the transcription $T1$ and $T3$ respectively and $S[T1, T1]$ is in fact the length of the transcription $T1$ - number of words (tokens):
$$ \begin{array}{cc} & \begin{array}{ccc} T0 & T1 & T2 & T3 & T* & Tn_s \\ \end{array} \\ S = \begin{array}{ccc}T0\\T1\\T2\\T3\\T*\\Tn_s \end{array} & \left[ \begin{array}{ccc} 21 & 5 & 3 & 1 & ... & 1 \\ * & 7 & 4 & 5 & ... & 0 \\ * & * & 32 & 1 & ... & 2 \\ * & * & * & 13 & ... & 0 \\ ... & ... & ... & ... & ... & ... \\ * & * & * & * & ... & 2 \end{array} \right] \end{array} $$
Given a fixed length $L$ for a batch / bin and $N_b$ the total number of batches, the objective is: \begin{align}\max&\quad\sum_n C_n\\\text{where}&\quad C_n=\sum_{i,\ j} S_{ij}, \forall n \in N_b, i \neq j, Ti \in B_n, Tj \in B_n\end{align}
Obviously that: \begin{align}&\quad N_b = \frac{N_s}{L}\\\text{and if}&\quad Ti \in B_n \implies Ti \notin B_m, \forall m \in N_b, n \neq m\end{align}
E.g. Let's say that every batch may only contain $L$ - 24 unique elements (transcriptions), for every batch, its 24 elements are only to be seen in that batch and not elsewhere. If there are 24 elements than there are $\frac{L * (L - 1)}{2}$ or 276 pairs that have to be referenced from the table $S$ and be summed together - $C_n$. Every batch has strictly a min and a maximum capacity of $L$, not more not less.
I know the problem is intractable to find an optimal solution, where adding another sub-objective to have also a balanced assignment where each batch has sufficiently high enough matches that alone will make it even harder, but I am wondering if there are any ways to relax the sub-problem mentioned above and get a suboptimal solution which is sufficiently good.
I tried the greedy approach but that results in many islands type of batches that have very low matches thus I am forced to discard them and remain with very few to work with.
I was also thinking about using a window-approach mode (as the $N_s$ is pretty large (20 000 - 1mln) and $L$ is low - 24 / 32). Thus, to perform a random assignment within a small window (subset of S, with smaller number of batches) and perform a certain number of swappings within a certain budget where each swap is valid (e.g. $Ta \in B_i, Tb \in B_g$) if it increases the $C_i + C_g$ before the swap + has some potential for parallelism.
