What algorithm will maximize utility when assigning of students to practicum locations I have the following problem: 
Students from a class of 150 are beginning practicum training. Students have the option of either staying in an urban centre for their practicum, or optionally, they can train in one of 12 rural locations.
Because the rural match is optional, there can be between 0 and 150 students trying to match to a rural location. 
11 of the rural locations can accommodate 2 students, the 12th can accommodate 1 student. 
The students rank order their location preferences from 1-12 (1 most desirable location, 12 least desirable location). 
If student's do not match to a rural location in their top 3 ranking, then they have the option of withdrawing from the rural match and doing their practicum at the urban centre with the rest of the class. 
The rural training locations have no input or preference as to which student(s) they receive. 
a) What is the best way to solve this problem in order to fairly match as many people to as many of their top locations as possible. i.e. to maximize utility 
b) How would the solution change if students were allowed to assign equal rankings to locations, or if some students had no preferences as to location, but just wanted to train at any rural location. 
Update:
This isn't homework. This is an actual real life problem that we have at our school.
Currently, applicants are selected out of a hat, so the process does not maximize utility.
To be clear, I am not looking for anyone to actually solve the problem for me. My (possibly erroneous) assumption is that this or similar problems have already been solved. And since neither my colleagues or I are trained in mathematics or computer science, we are probably just unaware that the solution exists.
What we are really looking for is someone to point us in the right direction.
I have looked at the Gale-Shapely algorithm, but as far as I can tell, it requires both sets to have rank order preferences, so I don't think it can be applied to our problem.
Any other suggestions?
 A: The kind of mathematics (other than Gale-Shapley) I'm aware of that might be relevant is voting theory.
I posted a few pointers here: https://stackoverflow.com/a/22569679/58668.
Here are the main features of your problem that seem relevant and a half-way decent match for voting theory:


*

*Voters/students give ordinal preferences—they state that they prefer outcome $a$ to outcome $b$, but not by how much.

*The "ballots" (statements of preference) are a ranking of various options, with ties allowed. However, the outcomes are complete assignments of students to places.


If student A prefers location 1 to all other locations, they are presumably indifferent between outcomes $(A:1, B:2, \ldots)$ and $(A:1, C:2, \ldots)$, but prefers $(A:1, B:2, \ldots)$ to $(B:1, A:2, \ldots)$. The ability of some locations to accept multiple students can be modeled by pretending to have two locations, "Johns Hopkins A" and "Johns Hopkins B" or whatever, which in reality refer to the same place.
This might end up being impractical if you need to work with a very large outcome space, e.g. of size 150 choose 12 or of size $150!$.
Note: I don't think that you can know that you're maximizing utility if you only have ordinal preferences—student A might prefer 1 to 2 by a lot while B prefers 1 to 2 by a little.  In that situation you maximize utility with $(A:1, B:2)$, but if all you know is "A: 1 > 2" and "B: 1 > 2" then you don't know whose preference is most intense. It might be that B had a more intense preference, in which case $(B: 1, A: 2)$ is the (only) utility-maximizing assignment.
You might also consider using Gale-Shapley in a way where you model the locations as having random preferences.  There was a link to a paper about school choice in a comment (What algorithm will maximize utility when assigning of students to practicum locations). The process described there did assign a random preference to schools as a tie-breaker.
Since students could hypothetically have completely identical preferences, breaking ties randomly is fair.  Better uniformly random than something arbitrary, like student name/id sorted alphabetically or "whichever happens first/last in my implementation of the algorithm".
If you use Gale-Shapley, I recommend giving students the "active" role ("proposer"?) in the GS framework, as the allocation is optimal for the active side but not necessarily the passive side ("reviewer", I think).
A: Hint: First place to start is reading about the Nobel Prize-winning Gale-Shapley algorithm which is used to match med students to first residencies, for example.
A: You can read https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs where you might consider your original problem as finding a maximum weight matching between students and programs where a student's third choice is connected to them by an edge with minimum positive weight $w_3 > 0$, and their second choice is connected to them by an edge with some weakly larger positive weight $w_2 \geq w_3$, and similarly the top choice is connected to them with some weakly larger edge weight $w_1 \geq w_2$. All other edges (outside the top 3 for a student) are assigned weight either weight 0 or some very small positive weight $\epsilon > 0$. There are efficient algorithms for this that you can read about at the link.
A: Here is the algorithm for problem (a)
Step 1
If the student decided to stay in the urban centre then let him stay in the urban centre (Because the urban centre can accommodate all students anyways) else if he decided not to stay then  go to Step 2
Step 2
Match the student to his top rural location if available else if occupied
then go to Step 3
Step 3
Match him to his second best rural location if available else if occupied
then go to Step 4
Step 4
Match him to his third best rural location of available else if occupied then go to Step 5
Step 5
Let the student stay in the Urban centre. Then Go Step 1 again untill all students are matched
Now how would you change this for question (b) ?
