Adding linear penalties for multiple assignments

Question

I have a multiple assignment problem, with an added cost for "repeat assignments".

For example, consider the cost matrix:

        sing  guitar  bass  drums
ringo      8      10    10      2
paul       3       4     2      5
john       2       4     4      5
george     4       2     4      5

If The Beatles are recording a single song, we can optimize this with standard OR tools, such as linear programming. We get the following assignment:

        sing  guitar  bass  drums
ringo      0       0     0      1
paul       0       0     1      0
john       1       0     0      0
george     0       1     0      0

Suppose that we are recording two songs. Being the polymaths that they are, The Beatles get bored playing the same roles in every single song, so they would really like to switch things up a bit. In other words, Paul could play bass on song 2, but he'd like to sing, maybe, so there is an added cost for him to play bass twice.

One way to incorporate this is to add a power on the assignment term in the objective equation. I.e. the "no multiple assignment penalty" objective equation for the regular assignment problem:

$ \sum c_{i,j} * x_{i,j} $

Becomes, say:

$ \sum c_{i,j} * x_{i,j}^2 $

So if Paul plays bass on song one and sings on song two, the overall cost due to Paul is $2*1 + 3*1 = 5$, but if Paul plays bass on both songs, then the overall cost due to Paul is not $2*2 = 4$, but $2*2^2 = 8$. We could adjust the $^2$ to be an arbitrary $^k$ for how much we want to penalize repeat assignments.

The problem with this approach is that the objective function is no longer linear. Is there a way to introduce penalties for multiple assignments, while keeping the problem linear?

Answer 1

One possible approach is to define an increasing sequence of cost coefficients $c_{ij}^{(k)}$ representing the costs of assigning $i\rightarrow j$ a total of $k$ times. In the objective function, introduce a new variable $z_{ij}$ for the cost of any $i\rightarrow j$ assignments, along with the constraints $$z_{ij} \ge c_{ij}^{(1)} x_{ij}$$ $$z_{ij} \ge c_{ij}^{(2)} (x_{ij} - 1)$$ $$\cdots$$ $$z_{ij} \ge c_{ij}^{(n)} (x_{ij} - n)$$ where $n$ is the upper limit on how many times the $i\rightarrow j$ assignment might be made. You will want the costs to satisfy $c_{ij}^{(2)} > 2 c_{ij}^{(1)},$ $c_{ij}^{(3)} > 2 c_{ij}^{(2)},$ etc.

Answer 2

Prof @prubin's solution is apt but if d.v. are needed to be raised to power k then, taking cue from geometric optimization (reference):
Introduce vars $z_{i,j}$
Objective = $log(\sum c_{i,j}\cdot e^{z_{i,j}})$
s.t.
$z_{i,j} \ge k\cdot log(x_{i,j})$