I have 20-80 users and 5-10 events with varying ranges of minimum and maximum number of free seats (2-4, 3-5, 2-6...). For example, with a range of 3-5 it is acceptable to only assign three users to the event. The users can choose weighted preferences (1,2,3) for 1-3 events. The problem is to assign as many as possible users to the events in an optimal way.
My current problem is how to allow the users to form predefined groups of varying sizes (2-8) before the optimization? The group cannot select an event if the maximum number of seats is smaller than the size of the group. This can be handled before the algorithm execution. The group can choose three weighted preferences in the same way as individual users. For example, out of 40 users there are three predefined groups of 4, 5, and 6 people and the remaining 25 users will be assigned individually.
My initial idea was to assign all users to predefined groups and then assign the groups to the events but I could not figure how to do it with varying groups sizes and event seats.
Non-optimal approximations and constraints that don't change the scope too much are also fine. There is a time constraint of ~30 seconds.
- Limit group size to two people. This is feasible because common scenario is that people want to join an event with one friend.
List of requirements:
- The goal is to assign as many users as possible to the events.
- User preferences must be honored.
- Events have minimum and maximum number of seats (for example: 3-5).
- If an event doesn't receive the minimum number of users, the event must be cancelled.
- Users can choose up to three (1-3) weighted preferences (1,2,3) for as many different events (1-3).
- Users can only be assigned to events they have chosen.
- If there are more users than free seats, the excessive users must be removed fairly.
- If users cannot be matched to their preferences, they must be removed. This should be the last measure.
- Users can form groups of varying sizes (2-8).
- Groups can choose three weighted preferences like individual users.
- The group cannot select an event if the maximum number of seats is smaller than the size of the group. This can be handled before the algorithm execution.
- Algorithm must be able to execute in under 30 seconds.
- Non-optimal approximations are fine.
- New constraints can be introduced if they don't change the scope too much.