7
$\begingroup$

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

1 Answers 1

7

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

In general, integer programming problems are NP-hard. The relaxed problem however is an ordinary linear programming problems and may be solved efficiently. Specialized software for mixed integer problems may be able to solve also the full problem efficiently.

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.

  • 0
    That is indeed correct - thank you. I am editing my post.2017-03-28