I want to split a group of people into subgroups. Each person has given me a list of at most 3 preferences of people they want to be in a group together with. Some people have given a list of fewer than 3 preferences, and some have none.
Constraints on subgroups are:
- Size of subgroup (max 40; as close to 40 as possible, so not groups of fewer than 25)
- Gender balance in subgroup (as close to balanced as possible)
Constraints on members are:
- I want to guarantee that each person is with at least 2 of their preferences.
I have been reading up on bipartite graph assignment problems, but I'm not sure if this problem is related. I don't think I can brute-force the problem, as the largest group is 450 people.
There is no miracle solution to combinatorial optimisation problems, but you can use "good" heuristics to find a solution :
For example, you create 12 groups of ~38 people with ~19W / ~19M
at each step, you change two people (always 2W or 2M) from 2 sets and you iterate. At the end, you chose the solution that gave you the highest score.
More difficult to implement. You go through the tree of possible sets recursivly and go back when you come to a non-satisfactory solution