How to configure Minimum Cost Maximum Flow to solve Unbalanced Assignment Problem?

Question

Problem

$n$ objects have to be assigned to $m$ categories, with $n \ge m$. Assigning an object $i \in [n]$ to a category $j \in [m]$ comes with a cost $c_{ij}$. Multiple objects can be mapped to the same category. All objects have to be assigned. All categories have to be used.

What I tried

Since it seems to be a special case of the Unbalanced Assignment Problem, I looked towards the Hungarian Algorithm. Unfortunately, the way this algorithm deals with unbalanced bipartite graphs does not seem to help much here - although I'm still looking in the litterature for an adequate extension, maybe here.

So I tried to map this problem to the Minimum Cost Maximum Flow Algorithm, but despite trying some parametrizations of the edges capacities, I can never guarantee that all the jobs are actually assigned and that all machines used.

For example, in the following picture all the $n=8$ objects (right set of vertices) could be assigned to a category, only 2 of the $m=3$ categories were used, what is not what I want.

Question

Is it possible to achieve the desired result under some specific configuration of the Minimum Cost Maximal Flow algorithm, or am I looking to the wrong algorithm?

Answer 1

Let $c_i^* = \min_{j \in [m]} c_{ij}$ be the minimum cost of assigning object $i$ to any category. If not for the constraint that all categories must be used, we would have a solution with cost $C^* := c_1^* + c_2^* + \dots + c_n^*$ just by giving each object its best category.

To satisfy that additional constraint, consider the matching problem where each category must be assigned an object (but not all objects have to be assigned), and the cost of assigning object $i$ to category $j$ is $c_{ij} - c_i^*$. (Think of this as the cost of "reassigning" object $i$ away from its best category.) This is equivalent to the original problem for the following reason:

• Suppose we solve the new problem. Extend this solution to solve the original problem, by giving each unassigned object its best category. Passing to the original problem, each object's cost increases by $c_i^*$, and so the total cost increases by $C^*$.
• Suppose we have an optimal solution to the original problem. Each category $j$ then contains at most one object $i$ such that $c_{ij} > c_i^*$ (if there are two such objects, we can reassign one of them to its best category and improve the cost). Pick such an object for each category; if a category contains no such objects, pick any object that's been assigned to that category. The result is an assignment of one object to each category, which is a solution to the new problem with total cost decreased by $C^*$.

Therefore if we solve the new problem optimally, we can get an optimal solution to the original problem.

---

How can we solve the new problem optimally? There are a few methods:

1. Create $n-m$ new categories for the new problem such that the cost of assigning any object to any of the new categories is $0$. Then, apply the Hungarian algorithm. Finally, forget the new categories we added.
2. Solve a minimum-cost flow problem where the source has a cost $0$ arc to each category, category $j$ has a cost $c_{ij}-c_i^*$ arc to object $i$, and each object has a cost $0$ arc to the sink. All arcs have capacity $1$. A flow of value $m$ with minimum cost (equivalently, a minimum-cost maximum flow) is exactly the matching we want.
3. I'm pretty sure that with this modification, the linked article "On Minimum-Cost Assignments in Unbalanced Bipartite Graphs" does exactly what we want.