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.

  • $\begingroup$ I don't understand the problem statement. Can you state it formally with mathematics? What is the objective function? I don't know what "batches total matches count" means. I suggest splitting this into multiple sentences -- it is hard to read your first sentence because there is so much in it. $\endgroup$
    – D.W.
    Aug 21, 2021 at 21:36
  • 1
    $\begingroup$ A problem that asks us to maximize one objective while minimizing another objective is not well-defined, because typically there will be a tradeoff between those two objectives, and you need to define precisely how you want to balance that tradeoff before this is well-defined. Typically the best way is to identify a single objective function you want to maximize. $\endgroup$
    – D.W.
    Aug 21, 2021 at 21:36
  • $\begingroup$ @D.W. Thanks for the feedback, I've updated the question (although I struggle a bit with MathJax), hope that it clarifies. $\endgroup$
    – DomainFlag
    Aug 22, 2021 at 9:18
  • $\begingroup$ What are the constraints on the pairs in each batch? Can one batch contain both $(i,j)$ and $(i',j)$? Can $(i,j)$ be present in two different batches? Do the union of the batches have to ensure that every item is matched somehow? etc.? What does the notation $Ti \in B_n$ mean? It appears that each batch $B_n$ is a set of pairs $(i,j)$. Please be consistent in your notation and mathematical formalization. $\endgroup$
    – D.W.
    Aug 22, 2021 at 19:54
  • $\begingroup$ @D.W. I've updated the question, $Ti \in B_n$ means that the transcript $T$ with index $i$ belongs only to the batch $B_n$. $\endgroup$
    – DomainFlag
    Aug 22, 2021 at 21:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.