Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
An algorithm to allocate optional modules to university students
#!/usr/bin/python
from gurobipy import *
from printtable import *
import random, string
print "=========================================================="
print "============ MODULE ALLOCATION: GUROBI SOLVER ============"
print "=========================================================="
# Generates fake University of York usernames
# e.g. Strings of the form xx###
def generate_username():
letters = "".join(random.choice(string.ascii_lowercase) for x in range(2))
numbers = "".join(random.choice(string.digits) for x in range(3))
return letters + numbers
# Takes a dictionary with tuples as the key, prints a 2D table using printtable.py
def dicttable(dict, table_title):
stud = set()
mod = set()
for x in sorted(dict.iterkeys()):
stud.add(x[0])
mod.add(x[1])
stud = sorted(stud)
header = [""] + stud
mod = sorted(mod)
allocs = []
for m in mod:
alloc = [m]
for s in stud:
try:
alloc.append(dict[s,m])
except KeyError:
alloc.append('')
allocs.append(alloc)
table = [header] + allocs
print "\n"
print table_title
pprint_table(out, table)
# Maps from rank -> coefficient
rank_coeff = {
0: 0,
1: 120,
2: 65,
3: 30,
4: 5,
5: 1,
6: 0,
7: 0
}
# sheets = ['UBCOMAMAT4']
students = {
'am639': {'routecode': 'UBCOMAMAT4'}
}
for i in range(14):
username = generate_username()
students[username] = {'routecode': 'UBCOMAMAT4'}
groups = {
'group1': {'routecode': 'UBCOMAMAT4', 'credits': 20},
'group2': {'routecode': 'UBCOMAMAT4', 'credits': 20}
}
modules = {
'CGO': {'group': 'group1', 'credits': 10, 'min': 5, 'max': 100},
'CRY': {'group': 'group1', 'credits': 10, 'min': 5, 'max': 100},
'CSW': {'group': 'group1', 'credits': 10, 'min': 5, 'max': 100},
'CGV': {'group': 'group1', 'credits': 10, 'min': 5, 'max': 100},
'PPS': {'group': 'group2', 'credits': 20, 'min': 5, 'max': 100},
'PR3': {'group': 'group2', 'credits': 20, 'min': 5, 'max': 100}
}
electives = {
('am639', 'group1'): {'credits': 10}
}
## Print the setup config
print ":: MODULE SETUP ::"
for group in groups:
print group + " (Route code: " + groups[group]['routecode'] + ", credits to be allocated: " + str(groups[group]['credits']) + ")"
for module in modules:
if modules[module]['group'] == group:
print " " + module + " (Credits: " + str(modules[module]['credits']) + ", class size: " + str(modules[module]['min']) + "-" + str(modules[module]['max']) + ")"
print "\n\n\n"
mavs = []
for student in students:
for group in groups:
if groups[group]['routecode'] == students[student]['routecode']:
for module in modules:
if modules[module]['group'] == group:
mavs.append((student, module))
ranking_prob = 1
ranks = {}
for mav in mavs:
if (random.random() < ranking_prob):
ranks[mav] = random.randint(1, 5)
# gurobimod_prefix = "zzz-mod_"
## GUROBI
try:
model = Model("modalloc") # new Gurobi model
# Create a binary variable for every student,module pair
# 1 indicates an allocation, 0 indicates no allocation
# These are named am639_POP, am639_CRY etc
gurobimavs = {}
for student, studentdata in students.items():
this_routecode = studentdata['routecode']
x_student = {}
gurobimavs[student] = x_student
for module, moduledata in modules.items():
if groups[moduledata['group']]['routecode'] == this_routecode:
x_student[module] = model.addVar(vtype=GRB.BINARY, name=student+"_"+module)
# Create a binary variable for each module
# 1 indicate module is running, 0 indicates it is not
gurobimods = {}
for module in modules:
gurobimods[module] = model.addVar(vtype=GRB.BINARY, name=module)
model.update()
# Objective function
objfn = LinExpr()
for student, dkt in gurobimavs.items():
for module, gurobivar in dkt.items():
# record objective coefficient
# for gurobivar based on ranking of module
# by student
try:
objfn.addTerms(rank_coeff[ranks[(student, module)]], gurobimavs[student][module])
except KeyError:
objfn.addTerms(0, gurobimavs[student][module])
# Hard constraint: student can only take module if it is running
for module in modules:
model.addConstr(gurobimavs[student][module] <= gurobimods[module], "modrunning")
model.setObjective(objfn, GRB.MAXIMIZE)
# Hard constraint: correct class size
for module in modules:
mylhs = LinExpr()
for student in students:
try:
mylhs.addTerms(1, gurobimavs[student][module])
except KeyError:
pass
# bounds, lower and upper
model.addConstr(mylhs - (modules[module]['min'] * gurobimods[module]) >= 0, "classmin")
model.addConstr(mylhs <= modules[module]['max'], "classmax")
# Hard constraint: correct number of credits
for student in students:
for group in groups:
# Sum this student's elective credits for this group
elective_credits = 0
for elective in electives:
if student == elective[0] and group == elective[1]:
elective_credits += electives[elective]['credits']
mylhs = LinExpr()
for module in modules:
if group == modules[module]['group']:
try:
mylhs.addTerms(modules[module]['credits'], gurobimavs[student][module])
except KeyError:
pass
model.addConstr(mylhs == groups[group]['credits'] - elective_credits, "credits")
# Hard constraints from departments (History has one exactly like this)
# The constraint is that a student cannot take both CGO and CGV - they can take one or the other
model.addConstr(gurobimavs[student]["CGO"] + gurobimavs[student]["CGV"] <= 1, "exclusives")
# Optimise!
model.optimize()
results = {}
for v in model.getVars():
try:
results[v.varName.split("_")[0],v.varName.split("_")[1]] = v.x
except IndexError:
# this is a module, not a student
pass
dicttable(ranks, ":: RANKINGS ::")
dicttable(results, ":: RESULT ::")
results_choices = {}
for result in results:
if results[result] == 1.0:
try:
results_choices[result] = ranks[result]
except KeyError:
results_choices[result] = "*"
elif results[result] == 0.0:
results_choices[result] = " "
dicttable(results_choices, ":: RESULTS WITH RANKINGS ::")
print "Obj:", model.objVal
except GurobiError, e:
print "\nWe've encountered a GurobiError\n"
print e
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment