I've spent a decent amount of time looking for the solution to the problem, which seems to be a variant of the assignment problem with constraints on the agents.

For a simple example, consider this:

A primary school has $m$ teachers who are to be assigned to teach $n$ courses. Each of these teachers is able to teach more than one but not all courses. For instance, Alice can teach Math and Chemistry, Bob can teach Chemistry and Physics, Cathy can teach Physics and Music, and so on. The goal is to design the assignment of teachers to the courses. Note that apparently a teacher not in the set of Music can't be assigned to the Music course. Assume there is no limit on how many courses each teacher can be assigned to, but each teacher should at least teach one course.

Mathematically, let us define $\textbf{X} \in \{0,1\}^{m \times n}$ as the assignment matrix where $x_{i,j}=1$ indicates that Teacher $i$ is assigned to Course $j$ and $x_{i,j}=0$ otherwise. For each course $j \in \{1,\cdots,n\}$, the set of available teachers is denoted by $\textbf{S}_j$.

Then, the constraints can be written as

$\sum\limits_{i \in \textbf{S}_j} x_{i,j} = \text{integer const}, \quad \forall j$

$\sum\limits_{j=1}^n x_{i,j} \geq 1, \quad \forall i $

The objective can be similarly formulated as the standard assignment problem.

Compared to the standard assignment problem, the main difference is that in the first constraint the sum is taken over a given set of agents instead of over all agents.

One possible approach that came to my mind is to write the constraints as the standard assignment problem, i.e., assuming $\textbf{S}_j = \{1,\cdots,m\}$ for any $j$, and impose a high cost for the non-existent edges between agents and tasks in the objective.

I appreciate it if anyone can shed any light on this problem. Thanks very much.

  • 2
    $\begingroup$ Start by defining your variables : let $x_{ij}\in \{0,1\}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ? $\endgroup$ – Kuifje Jan 15 at 19:16
  • $\begingroup$ @Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help. $\endgroup$ – J Zhao Jan 16 at 14:56
  • $\begingroup$ With $const:=1$, you are good. And just minimize $\sum_{i,j}c_{ij} x_{ij}$ $\endgroup$ – Kuifje Jan 16 at 15:04
  • $\begingroup$ @Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i \notin \textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks! $\endgroup$ – J Zhao Jan 16 at 15:59
  • $\begingroup$ I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine. $\endgroup$ – Kuifje Jan 16 at 20:13

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.