# A variant of assignment problem (different sizes of sets)

I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always holds that $|B| \leq |A|$, ie the number of b's will always be less or equal to number of a's.

The task is: For every $b \in B$ find some $a \in A$, minimizing the sum of individual costs, and satisfying the condition that every $b$ is assigned to exactly one $a$, and each $a$ is assigned to one or zero $b$s.

To state it clearly, the assignment satisfying the constraints is a bijective mapping $A^* \rightarrow B$, where $A^* \subseteq A$ and $|A^*|=|B|$.

I think this is a variant of the Assignment problem, but I'm not sure how to modify it to handle the case when the size of sets is not equal (some agents will be idle). Maybe the modification is not trivial, right?

Another idea would be to solve it by a brute-force algorithm assigning the closest unassigned $a$ for each $b$ (one after another) and backtracking when a better assignment for that $a$ is found later, but that's quite ugly.

How to find the optimal assignment efficiently (in polynomial time, if possible)?

This is a integer linear programming problem. Let $c_{ab}$ be the cost for the assignment$(a,b)$ and let $x_{ab}$ be 0 or 1 depending on whether this assignment is made or not. The goal is to minimize $$\sum_{a,b} c_{ab} x_{ab}$$ subject to the constraints $x_{ab} \in \{0,1\}$ and $\sum_a x_{ab} = 1$ for all $b$, $\sum_b x_{ab} \le 1$ for all $a$.
A natural relaxation is to replace the constraints $x_{ab} \in \{0,1\}$ with the inequalities $0 \le x_{ab} \le 1$.
Problems of this form with $|A|, |B| = O(10^2)$ can be solved in under 1 second in R using the lpSolve package. I don't know how well this scales to larger problem sizes.
• @Hans Engler: In the comment section of math.stackexchange.com/questions/2204953/…, Roloka raises an objection about your posted answer in this one. You state the constraint $$\text{For all}\;\,a,\;\sum_b x_{ab} = |B|$$ Roloka claims that instead you should have $$\text{For all}\;\,a,\;\sum_{b}x_{a,b}\le1$$ $$\text{For all}\;\,b,\;\sum_{a}x_{a,b}=1$$ It seems to me that Roloka's objection is valid. – quasi Mar 27 '17 at 19:59