1
$\begingroup$

I have an interesting assignment problem in which I have a cost matrix for workers and tasks, and need to assign each worker to exactly one task to minimize the cost.

However, this is all subject to the constraint that there must be no more than $k$ tasks being performed overall, by any worker.

I have not been able to find any literature about this specific problem and was wondering if it is known, and how best to solve it?

$\endgroup$
2
  • $\begingroup$ The question is a bit unclear. Can the same task be assigned to more than one worker? If not, should "assign each worker to a single task" be changed to "assign each worker to at most one task"? $\endgroup$
    – prubin
    Commented Nov 8, 2022 at 21:46
  • $\begingroup$ Sorry, yes, the same task can be assigned to more than one worker. But each worker must be assigned to exactly one task. I will update to make more clear. $\endgroup$
    – madhatter5
    Commented Nov 9, 2022 at 8:30

1 Answer 1

3
$\begingroup$

You could formulate it as an Integer linear program (ILP), then implement it in e.g. Pythons pulp library and ​solve it with a standard solver such as the open source COIN solver.

Based on the comment given below this answer, the ILP could then look as follows:

Let $t \in T$ be a task and $w\in W$ be the workers. The costs of assigning a worker $w$ to a task $t$ are given by $c_{wt}$.

DECISION VARIABLES

$x_{wt}$ Binary variable: $1$ if worker $w \in W$ is working on task $t \in T$ and $0$ if not.

$y_{t}$ Binary variable: $1$ if task $t \in T$ is performed and $0$ if not.

Linear Program \begin{align} \ & \min z = \sum_{w \in W}\sum_{t \in T} x_{wt} \cdot c_{wt} \; \\ \textit{S.t.}\\ \\ & \sum_{t \in T} x_{wt} = 1 & \forall w \in W \tag1 \\ & x_{wt} \leq y_t & \forall t \in T, w \in W \tag2 \\ & \sum_{t \in T} y_{t} \leq 3 & \tag3 \\ & x_{wt} \in \{0,1 \} & \forall w \in W, t \in T \tag4 \\ & y_{t} \in \{0,1 \} & \forall t \in T \tag5 \end{align}

The objective is to minimize overall costs. Constraint (1) assures that each worker is assigned to exactly one task. Constraint (2) assures that the binary variable $y$ is set to 1 if a worker is assigned to it. Constraint (3) assures that no more than 3 tasks are performed.

$\endgroup$
6
  • $\begingroup$ Thanks Peter! I apologize, I should have been more clear - each worker must be assigned to one task, but there cannot be more than (say) 3 tasks being performed overall. But it seems to be the same idea and maybe the best approach - I am currently trying something similar using the CP-SAT solver in ORtools but wasn't sure if there was a known solution to this $\endgroup$
    – madhatter5
    Commented Nov 8, 2022 at 17:42
  • $\begingroup$ @madhatter5 I updated my answer accordingly, including the ILP. I am not experienced with CP-SAT solvers and can therefore not tell you much about that. $\endgroup$
    – PeterD
    Commented Nov 8, 2022 at 17:54
  • 2
    $\begingroup$ To avoid big M issues, you can replace constraint (2) with $x_{wt}\le y_t$. $\endgroup$
    – Kuifje
    Commented Nov 8, 2022 at 18:04
  • $\begingroup$ @Kuifje I Updated the answer accordingly $\endgroup$
    – PeterD
    Commented Nov 8, 2022 at 18:08
  • $\begingroup$ For con(2) $\sum_w {x_{wt}} <= M*y_t$ for t in Tasks and where M could be total number of tasks. This will reduce the number of constraints. $\endgroup$ Commented Nov 10, 2022 at 0:10

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.