I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods. It's an single agent problem where we have to assign agent to perform exactly one task $j$ during each period $i$, i.e., $\sum_{j=1}^n x_{ij} = 1$ for $i=1,\ldots,m$ where $x_{ij}=1$ if agent is assigned to task $j$ in period $i$ and $0$ otherwise.We receive a reward of $c_{ij}$ for performing task $j$ on period $i$. Additionally, there is a penalty $p$ each time the task changes between two consecutive periods. If during period $i$ we assign the agent to perform task $j$ and on $i+1$ the task $j^\prime$, we subtract the penalty $p$ from the total reward of all assignments. We want to assign the agent in such way that the total profit $$\sum_{i=1}^m \sum_{j=1}^n x_{ij} c_{ij} - \text{penalties  introduced by changing task between periods}$$is maximized. I have been able to model this as an integer program with binary decision variables, but I was thinking maybe there is some other type of recursive algorithm (via dynamic programming) that could handle this problem also. Is this a known problem with solution methods present in literature? It seems like it could have already been studied, but I haven't been able to find a name for this kind of problem.
Discrete assignment problem with penalties
algorithms;optimization;dynamic programming;integer programming;assignment problem
Riley's answer is excellent.  It is possible to improve the running time further to $O(mn)$ time, using dynamic programming.  This saves a factor of $n$ in the running time.Define $T[i,j]$ to be the total profit of the best assignment for times $i,i+1,\dots,m$, assuming that at time $i$ the agent is assigned to task $j$.  We'll compute all of the $T[i,j]$ values, in order of decreasing $i$, using the following recurrence:$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j \le n, j' \ne j\} - p),$$or equivalently,$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j' \le n\} - p).$$Naively, it looks like filling in a single cell will take $O(n)$ time so computing all the $T[i,j]$ values will take $O(n^2)$ time.  However, we can speed it up with a trick.Define$$M[i] = \max(T[i,1],\dots,T[i,n]).$$We obtain the improved recurrence$$T[i,j] = c_{ij} + \max(T[i+1,j], M[i+1] - p).$$We'll fill in the $T[i,\cdot]$ and $M[i]$ values simultaneously, in order of decreasing $i$.   Once we've filled in $T[i,1],\dots,T[i,n]$, we can compute $M[i]$ in $O(n)$ time.  Then, once we know $M[i]$, we can compute each $T[i-1,j]$ in $O(1)$ time using the improved recurrence, so we can compute $T[i-1,1],\dots,T[i-1,n]$ in $O(n)$ time once we know $M[i]$.  Finally, $M[1]$ is the final answer to the problem.In this way, we do $O(n)$ work per value of $i$, and there are $m$ values of $i$.  Consequently, the total running time is $O(mn)$.