An algorithm to allocate optional modules to university students

modalloc.py

#!/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