I have a problem that I was able to conceptualize as following:
Suppose that there are n groups of agents A1, A2, …, An. Group Ai contains Ki agents where Ki is an integer between, say, 1 and 10. Note that different groups need not contain equally many agents (for example, group A1 may contain 5 agents and group A2 may contain 7 agents).
Suppose also that there are m factories F1, F2, … Fm. Factory Fj would like to employ at most Ej agents where Ej is an integer between, say, 1 and 10. Note that different factories may wish to employ a different number of agents (for example, factory F1 may wish to employ at most 3 agents and factory F2 may wish to employ at most 9 agents).
Each factory would like to employ groups of agents in different combinations under the restrictions
- List item If a factory employs one agent in a specific group then the factory must employ all agents in that group.
- List item Factory Fj can never employ more than Ej agents (for example, if A1 and A2 contains 4 agents and E1 = 7 then F1 can never employ the agents in the groups A1 and A2).
I would like the find the “matching” that employs the maximal number of agents.
Example: A1 contains 7 agents, A2 contains 4 agents and A3 contains 4 agents. There is only one factory (F1) and F1 would like to employ at most 8 agents. In this case the maximal matching is that F1 employs groups A2 and A3 (note that it is not possible to employ all agents in A1 and only one agent in A2 or A3 as a factory that employs one agent in a specific group must employ all agents in that group by assumption).
The problem can be described as a bipartite graph. I know that maximal matchings can be found using Edmunds (blossom) algorithm in the case without requirement 1). Suppose that I wish to find a maximal matching given requirements 1) and 2). How can this be achieved?