Grouping People On Preference

Hello all,
Newbie here looking for help. I am looking for help setting up an excel sheet to create groups based on peoples preference.

A little background, I have a friend that is a summer camp director. One of her responsibilities is creating groups for each cabin each week and many kids request to be with friends and many have multiple friend requests. Typically there are 240 kids per week and 24 cabins (10 campers/cabin). As you can imagine juggling all of these requests can be very time consuming and there is always an upset kid or parent because someone didn't get with someone else...you get the point. I am looking for help to create these groups that optimize matches if the kids are allowed to request cabin mates. I think if the requests are limited to one request per camper it would simplify things but on the other hand allowing up to three cabin mate requests would allow for more flexibility? The next (more complicated step) would be all of this weighted on preference of cabin mates, i.e. on the application it might read "list requested cabin mates in order of preference 1-3", The last part may be me just over-complicating things.


Thanks in advance for any help!

Newbie

Hey there,

So the problem you are describing will require solver - the problem is, that free version only allows for 200 variable cells (camper assignments to cabins) and the paid version only allows for 2,000 variable cells. Your problem has 2,400 - i.e. 240 campers with 10 possible assigments (240*10)

attached is a workbook that has set up the problem - if you want to try the solver free trial and limit the problem to 2000 or limit the problem to 200 and use the free version, this setup should work for you. I can't guarantee as I haven't been able to run it.

Link to solver premium trial http://www.solver.com/premium-solver-pro

Link to enabling solver (free or otherwise) http://office.microsoft.com/en-us/ex...010021570.aspx

If you still need assistance in running a smaller version of the problem let me know - if some campers (at least 40) don't put any preference you could run the problem with 2000 and randomly assign the remaining 40 campers to cabins.

WOW, that was quick.

Would the use of Solver still be required if the preferences were not weighted? I think weighting the preferences would be ideal in a digital world but may just complicate things for her. If possible, I would like to see a simpler sheet with no weights and the maximum number of preferences limited to three but could be modified for one max or two max preferences.

I will ask her how many campers actually submit cabin mate requests. This number could be much lower than I imagined so a free version may be adequate. One more thing I forgot to mention is the number of possible combinations are only half of what you thought them to be since cabin mates are always of the same gender.

Thanks again!

Hi all, I have a similar question and i think this solver feature will help me. I am hosting a think tank and each participant will select 3 people they want to work with on future collaborative projects. I have downloaded the camper assignment but unfortunately, I'm only somewhat savvy with excel. Can some please please kindly give me a more step by step instruction on how to group the participants into groups of 3 or 4. I will have about 30 participants in total. Thank you.

The need of solver is to optimize the solution - there maybe (likely are) ways to do this sub-optimal using more by hand methods or through VBA programming but solver is your easiest bet. The weights add to complexity but not significantly (from my understanding of linear programming).

With the number down to 120 campers and 12 cabins you have 1440 variable cells so the paid version of solver should work (depending on how many times this needs to be done the 15 day trial may be enough). However, the solver paid version is $1,000 so it is likely cost prohibitive for just this exercise.

Currently you could set the weights all to one and have campers choose preference from 0-3 so if you only have one or two preferences you only enter one or two preferences and essentially remove weighting. The real limitations you are facing is the number of campers that need to be assigned. With actually camper preferences, you could make smaller problems that only handle groups of campers who have requests that are tied to each other but the free version limits you to 20 campers and 10 cabins at a time (200 variables) which is fairly small and could likely be done by hand.

I have attached the smaller version assuming half male and half female (you would copy and run twice for each set) - I also removed the weighting. However, the problem still exists with the 1440 decision variables. If you have real data I would be happy to setup my solver trial and try and run it to check results.

Sorry for the rambling post and happy to help.

- melk

Thank you for sharing!

Dear,

I'd like to provide a linear programming idea here by using 30 students & 5 groups.

It is recommended to use an open source solver named "Open Solver".
The decision variables are : Xij, assign student i in group j.
The typical constraints are:
1) each student is assigned in only one group.
2) each group containts 6 students(30 students in 5 groups).

To apply the preference constraints, typically there are two methods:
1) multiply the assignment choice for the two students, sum up and then maximize it. For example, if the 2 students are in the same group, that the two students will have a score of 2, if not in the same group, the score will be 0. This will force Solver to put the two students in the same group. This is a nonlinear programming - Because the two variables are multiplying with each other.
2) use minMax method, introduce a set of binary variables, Ytj
Ytj >= Xnj - Xkj, and then minimize Sum of Wj*Ytj, Wj is the weight we set, which is constant.
This is a linear programming.