0

We have a maximum bipartite matching problem such that M people need to be assigned N slots such that each slot has at-least one person and a subset of M people will have one out of these N slots each, while others will have 2 of these slots allocated to them.

For example: 8 slots, 6 people. 4 of these people will only need to cover 1 slot each but other 2 will cover 2 each. Hence, all 8 slots will be allocated (4*1 + 2*2).

The input data will reflect which of the M people will cover 1 slot each and which will cover 2 slots each.

We have the following implementation using HopCroft Carp so far:

from hopcroftkarp import HopcroftKarp
graph = {'john': {12, 3, 5}, 'june': {5, 10, 8}, 'joe': {5, 3}}
HopcroftKarp(graph).maximum_matching(keys_only=True)
>> {'joe': 3, 'june': 5, 'john': 12}

To further complicate the issue, each of the users can indicate one of 3 choices: preferred, not preferred but available and conflict (not available).

How do we allocate slots to people such that most people get preferred slots and then 'preferred but not available slots' and nobody gets 'not available'? How do we adapt our existing information above to take into account these 3 choices that people have? Also, how do we further reflect that some people need to be allocated 2 slots?

We have looked at similar questions, however they carry only 2 choices for people available or not available.

learnerX
  • 1,022
  • 1
  • 18
  • 44
  • 1
    You have to have some sort of cost function to minimize, otherwise it's very broad/vague. i.e. what's weighted more - a person getting a preferred slot or someone avoiding a conflict, would you sacrifice 2 slots being allocated by one person in favor of those slots being used by two people? etc. Ideally you want some objective function to minimize, like `cost = 1 * n_conflict + 0.5 * n_available` – Primusa Dec 30 '19 at 03:58
  • Thanks, we did end up implementing an objective cost function and found a well-known algorithm to reduce the overall assignment cost: https://en.wikipedia.org/wiki/Hungarian_algorithm – learnerX Jan 02 '20 at 01:47

0 Answers0