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