Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  alex.jordan Apr 17 '12 at 7:01
    
Yes, I'm willing to accept a 'good enough' solution. –  mjibson Apr 17 '12 at 15:15
    
The Hungarian method (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... –  Hauke Strasdat Apr 19 '12 at 17:06
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.