Discrete assignment problem with penalties

Question

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.

Answer 1

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)$.

Answer 2

First, you can model the task management as a directed graph. Suppose you have a source node $a$, a sink node $b$, and $mn$ nodes, one for each task. We say that $v_{ij}$ represents the $j$th task on the $i$th time period. The edges are as follows.

$$E=\{(a,v_{11}),(a,v_{12}),\dots,(a,v_{1n})\}\cup\\\{(v_{ij},v_{(i+1)j'})\vert 1\leq i<m,1\leq j\leq n, 1\leq j'\leq n\}\cup\\\{(v_{m1},b),(v_{m2},b),\dots (v_{mn},b)\}$$

Basically, the source node connects to each task in the first time period, each combination of tasks in adjacent time periods are connected, and the tasks on the final time period are connected to the sink node. The weight of an edge $(v_{ij},v_{(i+1)j'})$ is $c_{(i+1)j'}$ if $j=j'$ and $c_{(i+1)j'}-p$ otherwise. The weight of an edge $(a,v_{1j})$ is $c_{1j}$, and the weight of an edge to the sink is $0$.

The goal is to find the maximum path from $a$ to $b$. Since this is a directed acyclic graph, this can be done in $O(V+E)$ time, according to GeeksforGeeks. There are $mn+2$ vertices and $(m-1)n^2+2n$ edges, so the overall time complexity is $O(mn^2)$.