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
    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