1
$\begingroup$

I have an assignment problem. There are $N$ tasks and $M$ people. Assigning job $i$ to person $j$ will result in a profit of $p_{ij}$ and also comes with various other parameters, say, stress of $s_{ij}$, energy of $e_{ij}$, and cost of $c_{ij}$. A person should be assigned at most one job and a job should be assigned to at most one person. The sum of the stress from all assignments should not be more than $S$. Similarly, the sum of the energy should not be more than $E$ and the sum of the cost should not be more than $C$. Assign the jobs to people such that the profit is maximized while meeting the above constraints. The above assignment is formulated as an optimization problem as follows:

$\underset{x_{ij}}\max \sum_{i=1}^N \sum_{j=1}^{M} x_{ij} p_{ij}$

s.t. $\sum_{i=1}^N x_{ij} \leq 1, \ \ \forall j$,

$\sum_{j=1}^{M} x_{ij} \leq 1, \ \ \forall i$,

$\sum_{i=1}^N \sum_{j=1}^{M} x_{ij} s_{ij} \leq S$

$\sum_{i=1}^N \sum_{j=1}^{M} x_{ij} e_{ij} \leq E$

$\sum_{i=1}^N \sum_{j=1}^{M} x_{ij} c_{ij} \leq C$

$x_{ij} \in \{0,1\} \ \forall i, j$.

Is the above problem a specific case of a well-known problem?. If so what is it called?

Is there a polynomial-time algorithm that solves this problem either optimally or with approximation guarantees. Thanks in advance.

$\endgroup$
  • $\begingroup$ So what's your question? If you have a specific combination of numerical values for the inputs, then provide them to a solver to produce a solution for that problem instance. $\endgroup$ – Mark L. Stone Aug 5 '18 at 13:55
  • $\begingroup$ If you are referring to the exhaustive search, then the number of combinations for the inputs are 2^(MN), which are computationally not feasible. The question is there a polynomial time algorithm that solves this problem either optimally or with approximation guarantees. $\endgroup$ – Bala Aug 7 '18 at 3:29
  • $\begingroup$ Have you looked into "LP rounding"? You can try to relax the problem to a linear program by letting $x_{ij} \in [0,1]$. Then round the solution of LP in some way to get back an integer result. There is a lot of research on how to get good approximations this way or when the LP solution is exact. Another keyword to search is the "integrality gap". $\endgroup$ – passerby51 Aug 7 '18 at 3:42

Your Answer

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

Browse other questions tagged or ask your own question.