I have a list of positive nonzero integers $T=[v_1,\dots,v_𝑛|v_𝑖\in Z^{\neq}]$ which sum up to $V=\sum_i v_i$. Typically, the length of T (number of integers) goes from 100 to 1000. The list is not sorted, i.e., there's no guarantee that $v_i\leq v_{i+1}\ \forall\ i.$ Each integer can be be assigned either to a set $S_1$ or a set $S_2$: equivalently, it can be labeled as $l_1$ or $l_2$. The objective is to label $v_1,\dots,v_n$ so that

$$\sum_{v_i\in S_1} v_i = 0.3V \tag{1}$$ $$\sum_{v_i\in S_2} v_i = 0.7V \tag{2}$$

i.e., to minimize the cost $$L=\left(\sum_{v_i\in S_1} v_i - 0.3V\right)^2$$

Up to this point, the problem would be fairly trivial and it definitely wouldn't require AI. However, there are a couple additional details: the integers must be labeled in the sequence they appear ($v_1$ first, then $v_2$, etc.), and each time we "switch" label, we incur a cost. In other words, if the agent assigns $v_1$ to $S_1$, then $v_2$ to $S_2$, then $v_3$ to $S_1$, etc., it should be penalized for that.

I was thinking of formalizing this by counting the number $m$ of switches (of course $m\geq 1$) and adding it to $L$, i.e. by modifying the cost function to

$$L'=\left(\sum_{v_i\in S_1} v_i - 0.3V\right)^2+\beta m^2$$

where $\beta$ is a positive parameter, which I could use to weight the two objectives.

Would it make sense to cast this as a Reinforcement Learning problem? Or is it more appropriately an AI planning problem? Can you suggest an efficient algorithm to solve it?

  • $\begingroup$ Any constraints on size of list L, or typical sizes that you are dealing with? BTW you have used $L$ both as the list name and as name for your loss function, which caused me a moment of confusion . .. $\endgroup$ – Neil Slater Jan 24 at 14:34
  • $\begingroup$ @NeilSlater you're absolutely right that using the same letter for the cost function and the list is bad. See my edit. $\endgroup$ – DeltaIV Jan 24 at 15:46
  • $\begingroup$ @NeilSlater typical lengths for T: from $\sim 100$ to $\sim 1000$ $\endgroup$ – DeltaIV Jan 24 at 15:47
  • $\begingroup$ Thanks, I do not know the answer here (although I know enough to have a go at the issue, I would not be certain I was using anything like the best technique). Knowing the scale of the problem can identify whether you might use an exact solver that always got minimum cost for instance. I think the question is interesting and on-topic here $\endgroup$ – Neil Slater Jan 24 at 16:01
  • $\begingroup$ Another place this question might be on topic: or.stackexchange.com $\endgroup$ – Neil Slater Jan 24 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.