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?


2 Answers 2


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.

  • 1
    $\begingroup$ This general technique seems to extend nicely to all sorts of situations where I have additional costs for various assignment configurations. $\endgroup$
    – Him
    Jan 18, 2023 at 20:39

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}})$
$z_{i,j} \ge k\cdot log(x_{i,j})$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.