patternMinor
Discrete assignment problem with penalties
Viewed 0 times
problemwithpenaltiesdiscreteassignment
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#69720, answer score: 3
Revisions (0)
No revisions yet.