Solving a many-to-one assignment problem with additional constraints

Question

Assume there are $M$ items and $N$ people with $M \ge N$. A single item can be assigned to more than one person; however, item $i$ cannot be assigned more than $d_i$ times in total. Furthermore, each item has a category $c_i$ and a single person cannot be assigned two or more items of the same category.

The assignment of item $i$ to person $p$ produces value $v_{i, p}$. I would like to find an assignment which maximizes the total value.

It should be fairly simple to write this as an, e.g., MiniZinc model. What I am interested is whether this resembles some optimization problem that has already been researched.

Μάρκος Καραμέρης · Answer 1 · 2018-08-08T12:21:12.910

1

Your problem is actually more manageable with a greedy approach: 1) short the $v_{i,p}$ values into a list 2) for each person $p$ keep a category table where $u_p(x)=1$ if category $x$ is used and $0$ otherwise. 3) starting from the top assign the maximum value $v_{i,p}$ to the total sum if $d_i>0$ and the category of item $i$ is not used by person $p$ and then assign $d_i:=d_i-1$ and set $u_p(x)=1$. 4) the algorithm terminates when you reach the bottom value and takes time $MN$. It isn’t hard to prove that the correctness of this algorithm.

edited Aug 08 '18 at 12:21

answered Aug 06 '18 at 11:23

Μάρκος Καραμέρης

1,748
11
22

How would this maximize the total value? – d125q Aug 06 '18 at 12:38
Because maximum flow implies maximum matching in your person-item graph. The item category nodes are just for the additional $c_i$ constraints. If you read the max flow min cut algorithm on Wikipedia you will find all sorts of such applications. – Μάρκος Καραμέρης Aug 07 '18 at 12:00
Yes, but the flow is in no way influenced by the values $v_{i, p}$. – d125q Aug 07 '18 at 12:34
I thought $v_{i,p}$ was $1$ or $0$ depending on if a path person-category-item exists (has flow coming through it) or doesn’t exist – Μάρκος Καραμέρης Aug 07 '18 at 14:17
If I misunderstood your question please provide more details on what $v$ is – Μάρκος Καραμέρης Aug 07 '18 at 14:18
No -- as I said, $v_{i, p}$ is the value/utility person $p$ gets from being assigned item $i$. – d125q Aug 07 '18 at 14:26
Ok then, since I am writing from a mobile device I will delete or edit my answer as soon as I get back to desktop. – Μάρκος Καραμέρης Aug 07 '18 at 14:42
I think you could still pull this off with a greedy approach where you start from each person and follow the flow path all the way to the optimal item from each category that was chosen. As I said though I will try to edit this into a complete answer. – Μάρκος Καραμέρης Aug 07 '18 at 14:46

Solving a many-to-one assignment problem with additional constraints

1 Answers1