2
$\begingroup$

I have 30 users and 7 groups. All users will be members of exactly 2 groups. Each group must have between 4 and 6 members. The users have ordered their preferences for group membership (i.e., users have listed in order the groups they would like to be apart of). I would like a solution that assigns all users to groups that minimizes the total distance of all users from their top group preference.

I am trying to find a solution to this problem that is not a brute force calculation (as the search space is quite large). Is there a way to pose this problem such that it would be solvable by some optimization technique? It appears to be non-linear and non-smooth, which reduces the types of solutions, but I still can't figure out how to write the constraints. Or is there an entirely better way to solve this?

  • 0
    This sounds like one of those problems where you may have to take some naive algorithm, accept that its result won't be optimal, but prove that its result is somehow decent.2012-04-17
  • 0
    Yes, I'm willing to accept a 'good enough' solution.2012-04-17
  • 0
    The Hungarian method (http://en.wikipedia.org/wiki/Hungarian_algorithm) might to be applicable, which runs in polynomial time. Not 100% sure, it might need some adaptation. Don't have time to get my head around...2012-04-19

1 Answers 1

2

Don't know if you're still looking for a solution, but it is a straight forward 0/1/ assignment model. 210 dec variables, 30 constraints for each user, 14 constraints (2 for each group) for groups, objective function is simply the (7-order) and it is a maximization.

Problem with your objective function is that there will likely be alternative optimal solutions given that the measure of preference is ordinal - there are ways in which we might implement different objectives for 'fairness' - minimize the maximum difference from the most preferred for all users, etc.

If you have the preference data in a "matrix"-style on a spreadsheet, I can get you a solution within minutes.

Interesting problem. Fish Doc