Variant of assignment problem

Question

This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to find an assignment matrix $A$ which is again an $n \times m$ binary matrix (contains ones and zeros) and if $A_{ij}$ is $1$ it shows $i$-th person from first group has assigned to $j$-th person of second group, and maximize $\displaystyle\sum_{i}\sum_{j} C_{ij}A_{ij}$, subject to following constraints:

$$ 1)\;\; \forall i: \;\; \displaystyle\sum_{j} A_{ij} = 1 \\ 2)\;\; \forall j: \;\; \displaystyle\sum_{i} A_{ij} \le 2 $$

how should I solve this problem?

*how should we solve if we have another matrix $D$ and we also want $\displaystyle\sum_{i} D_{ij}A_{ij} \le constant$ ?

Answer 1

You want to assign $n$ persons to $m$ groups, so that

1. Each person is assigned one group.
2. Each group is assigned at most two people.
3. For each possible person $i$ and group $j$ there is a score $C_{ij}$, and you want to maximize the sum of scores of all assignments.

If such an assignment is at all possible, then $n \leq 2m$.

Create an instance of the usual assignment problem (in which we are looking for a one-to-one correspondence between persons and groups) as follows:

• There are $n$ real persons $1,\ldots,n$ and $2m-n$ dummy persons $n+1,\ldots,2m$.
• There are $2m$ groups, composed of two copies of the original groups: $1,\ldots,m$ and $m+1,\ldots,2m$.
• The costs $C'_{ij}$ of the instance are: for $i \in \{1,\ldots,n\}$ and $j \in \{1,\ldots,m\}$, define $C'_{ij} = C'_{i(j+m)} = C_{ij}$, and set all other costs to zero.

Every feasible solution of the original problem translates to a feasible solution of the new problem with identical cost, and vice versa.