I am trying to solve a variation of linear assignment problem:

The problem has an equal number of agents and a number of tasks. Any agent can be assigned to perform any task, and for each agent we know the probability that he will succeed performing the task (p > 0). It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total probability of success (product of all chosen probabilities) of the assignment is maximized.

I currently have no ideas, although this problem is similar to weapon target assignment problem but much more easier. We probably could try to replace cost function and multiplication with addition to solve general linear assignment problem then, but I don't know how.

I'd really appreciate if anyone can help me with ideas or solution (because this problem seems like a standard one to me).


The objective function is $\prod_{1 \le i, j \le n} p_{i j}^{x_{i j}}$, which can be linearized by taking logarithms as:

$$\sum_{i, j} x_{i, j} \ln p_{i, j}$$

But this is still a integer (0-1) linear program.

  • $\begingroup$ But $p_ {ij}^0 > p_ {ij}^1$ $\endgroup$ – callculus Nov 19 '15 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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