# Can I solve this assignment problem with RL or AI planning, and if yes how?

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?

• 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 . .. – Neil Slater Jan 24 at 14:34
• @NeilSlater you're absolutely right that using the same letter for the cost function and the list is bad. See my edit. – DeltaIV Jan 24 at 15:46
• @NeilSlater typical lengths for T: from $\sim 100$ to $\sim 1000$ – DeltaIV Jan 24 at 15:47
• 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 – Neil Slater Jan 24 at 16:01
• Another place this question might be on topic: or.stackexchange.com – Neil Slater Jan 24 at 16:02