Body: <p>I have a list of positive nonzero integers <span class="math-container">$T=[v_1,\dots,v_|v_\in Z^{\neq}]$</span> which sum up to <span class="math-container">$V=\sum_i v_i$</span>. Typically, the length of T (number of integers) goes from 100 to 1000. The list is <strong>not sorted</strong>, i.e., there's no guarantee that <span class="math-container">$v_i\leq v_{i+1}\ \forall\ i.$</span> Each integer can be be assigned either to a set <span class="math-container">$S_1$</span> or a set <span class="math-container">$S_2$</span>: equivalently, it can be labeled as <span class="math-container">$l_1$</span> or <span class="math-container">$l_2$</span>. The objective is to label <span class="math-container">$v_1,\dots,v_n$</span> so that </p>
  
  <p><span class="math-container">$$\sum_{v_i\in S_1} v_i = 0.3V \tag{1}$$</span> 
  <span class="math-container">$$\sum_{v_i\in S_2} v_i = 0.7V \tag{2}$$</span> </p>
  
  <p>i.e., to minimize the cost 
  <span class="math-container">$$L=\left(\sum_{v_i\in S_1} v_i - 0.3V\right)^2$$</span></p>
  
  <p>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 (<span class="math-container">$v_1$</span> first, then <span class="math-container">$v_2$</span>, etc.), and each time we "switch" label, we incur a cost. In other words, if the agent assigns <span class="math-container">$v_1$</span> to <span class="math-container">$S_1$</span>, then <span class="math-container">$v_2$</span> to <span class="math-container">$S_2$</span>, then <span class="math-container">$v_3$</span> to <span class="math-container">$S_1$</span>, etc., it should be penalized for that. </p>
  
  <p>I was thinking of formalizing this by counting the number <span class="math-container">$m$</span> of switches (of course <span class="math-container">$m\geq 1$</span>) and adding it to <span class="math-container">$L$</span>, i.e. by modifying the cost function to</p>
  
  <p><span class="math-container">$$L'=\left(\sum_{v_i\in S_1} v_i - 0.3V\right)^2+\beta m^2$$</span></p>
  
  <p>where <span class="math-container">$\beta$</span> is a positive parameter, which I could use to weight the two objectives.</p>
  
  <p>Would it make sense to cast this as a Reinforcement Learning problem? Or is it more appropriately an <a href="https://en.wikipedia.org/wiki/Automated_planning_and_scheduling" rel="nofollow noreferrer">AI planning</a> problem? Can you suggest an efficient algorithm to solve it?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T14:34:34.057Z
Comments.Text: 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 . ..
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T15:46:20.243Z
Comments.Text: @NeilSlater you're absolutely right that using the same letter for the cost function _and_ the list is bad. See my edit.
Comments.UserDisplayName: DeltaIV
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T15:47:30.167Z
Comments.Text: @NeilSlater typical lengths for T: from $\sim 100$ to $\sim 1000$
Comments.UserDisplayName: DeltaIV
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T16:01:42.320Z
Comments.Text: 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
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T16:02:47.750Z
Comments.Text: Another place this question might be on topic: https://or.stackexchange.com/
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-24T16:42:25.830Z
Comments.Text: @NeilSlater even a solution which doesn't reach optimum cost always, but at least very often, would be useful.
Comments.UserDisplayName: DeltaIV
Tags: <reinforcement-learning><planning>
Title: Can I solve this assignment problem with RL or AI planning, and if yes how?
UserDisplayName: DeltaIV
ThreadText: # Can I solve this assignment problem with RL or AI planning, and if yes how?
  
  (Asked by: username_0 on 2020-01-24)
  
  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](https://en.wikipedia.org/wiki/Automated_planning_and_scheduling) problem? Can you suggest an efficient algorithm to solve it?
  
  **Tags:** reinforcement-learning, planning
  > **Comments:**
  > **username_1**: 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 . ..  
  > **username_0**: @NeilSlater you're absolutely right that using the same letter for the cost function _and_ the list is bad. See my edit.  
  > **username_0**: @NeilSlater typical lengths for T: from $\sim 100$ to $\sim 1000$  
  > **username_1**: 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  
  > **username_1**: Another place this question might be on topic: https://or.stackexchange.com/  
  > **username_0**: @NeilSlater even a solution which doesn't reach optimum cost always, but at least very often, would be useful.  
  
  ---
  
  ## 0 answers
  
  