I have a bi-partite graph $G=(P \cup C,E)$ where $P$ contains 'parents', these parents are in pairs, but count as one vertex, and are to be matched with a number of children in the set $C$. I want to add a constraint that 'families', that is a group of pairings, should have $c$ children such that $1 \leq c \leq 4$ (Ideally it would be evenly spread but that doesn't really matter.)
I will have a cost function $\lambda: P \times C \to \mathbb{R}$ that will, given a parent-pair and some information about them and a child give a score of how good a pairing they would be. Presume this function is given.
The goal: to have families all matched as well as possible (i.e. maximise $\lambda$ either in each case, or as an average overall, or smth) as per the function $\lambda$. Cost is not determined based on other children already in the family, just the parents. Can anyone point me to an algorithm that could solve this, or requires minimal modification to solve it?
I cannot brute force as that would be $\mathcal{O}(N!)$ and my inputs could be as large as $N=500$. Note: since this is for practical usage a non-perfect but very good solution is acceptable. Although, I'd obviously love a perfect solution.
I have seen the Hungarian Algorithm but I don't know how I'd modify it to allow multiple assignments per parent-pair. If it can be done please refer me to a source stating how :)
You can introduce three additional copies of each node in $P$, yielding $4|P|$ parent nodes, and also introduce $4|P|-|C|$ dummy child nodes to balance the two sides of the bipartition. To force at least one real child per parent, impose a large negative $\lambda$ for the first parent node out of each four to each dummy child node. All other pairs $(p,c)$ where $c$ is a dummy child node have $\lambda(p,c) = 0$. Now solve the usual $n \times n$ maximum assignment problem with the Hungarian algorithm or otherwise.
An alternative approach is solve a transportation problem in the original network, with a (variable) supply in $[1,4]$ for each parent node, and a demand of at most $1$ per child. You can use a network flow solver or a linear programming solver.