1
$\begingroup$

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.

I'm using Hungarian algorithm and the JavaScript implementation is done using munkres-js. If there is no solution, events and finally users can be dropped until there is a solution. This produces satisfactory non-optimal solutions.

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.

Any ideas?

// EDIT

Proposed constraints:

  • Limit group size to two people. This is feasible because common scenario is that people want to join an event with one friend.

// EDIT2

List of requirements:

  • Goal

    • The goal is to assign as many users as possible to the events.
    • User preferences must be honored.
  • Events

    • 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.
  • Individual users

    • 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.
  • Groups

    • 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.
  • Other

    • 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.
$\endgroup$
  • $\begingroup$ If players form a group and try to find a game as a group, do they then also get to have individual preferences? $\endgroup$ – Tommi Brander May 18 '18 at 8:29
  • 1
    $\begingroup$ No. There is a group leader who will choose the events (games) to sign up for. $\endgroup$ – Archinowsk May 18 '18 at 14:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.