# Variant of assignment problem

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$$ ?

• Isn't there a confusion between $X$ and $A$? If not, what is $X$ and how is $A$ used? Commented Mar 31, 2021 at 16:23
• oh yes, it was my fault, they are the same things, I just edited the post, thanks Commented Mar 31, 2021 at 17:15

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.