algorithm - Sorting People into Groups based on Votes

Question

I have a problem with finding a algorithm for sorting a dataset of people. I try to explain as detailed as possible:

The story starts with a survey. A bunch of people, lets say 600 can choose between 20-25 projects. They make a #1-wish, #2-wish and #3-wish, where #1 is the most wanted project they want to take part and wish 3 the "not-perfect-but-most-acceptable-choose".

These project are limited in their number of participants. Every project can join around 30 people (based on the number of people and count of projects).

The algorithm puts the people in the different projects and should find the best possible combination.

The problem is that you can't just put all the people with their number 1 wish X in the certain project and stuff all the other with also number 1 wish X in there number 2 wish because that would not be the most "happiest" situation for everybody.

You may can think of what I mean when you imagine that for everybody who get his number 1 wish you get 100 points, for everybody who get his number 2 wish 60 points, number 3 wish 30 points and who get not in one of his wishes 0 points. And you want to get as most points as possible.

I hope you get my problem. This is for a school-project day. Is there something out there that could help me? Do you have any idea? I would be thankful for every tipp!!

Kind regards

Answer 1

You can solve this optimally by formulating it as a min cost network flow problem.

Add a node for each person, and one for each project.

Set cost for a flow between a person and a project according to their preferences.

(As Networkx provides a min cost flow, but not max cost flow I have set the costs to be negative.)

For example, using Networkx and Python:

import networkx as nx

G=nx.DiGraph()

prefs={'Tom':['Project1','Project2','Project3'],
       'Dick':['Project2','Project1','Project3'],
       'Harry':['Project1','Project3','Project1']}

capacities={'Project1':2,'Project2':10,'Project3':4}

num_persons=len(prefs)
G.add_node('dest',demand=num_persons)
A=[]
for person,projectlist in prefs.items():
    G.add_node(person,demand=-1)
    for i,project in enumerate(projectlist):
        if i==0:
            cost=-100 # happy to assign first choices
        elif i==1:
            cost=-60 # slightly unhappy to assign second choices
        else:
            cost=-30 # very unhappy to assign third choices
        G.add_edge(person,project,capacity=1,weight=cost) # Edge taken if person does this project

for project,c in capacities.items():
        G.add_edge(project,'dest',capacity=c,weight=0)

flowdict = nx.min_cost_flow(G)
for person in prefs:
    for project,flow in flowdict[person].items():
        if flow:
            print person,'joins',project

In this code Tom's number 1 choice is Project1, followed by Project2, then Project3.

The capacities dictionary specifies the upper limit on how many people can join each project.