diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | README.md | 20 | ||||
| -rwxr-xr-x | assignment.py | 145 | ||||
| -rw-r--r-- | input.toml | 16 | ||||
| -rw-r--r-- | requirements.txt | 2 |
5 files changed, 184 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..21d0b89 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +.venv/ diff --git a/README.md b/README.md new file mode 100644 index 0000000..efdeb8b --- /dev/null +++ b/README.md @@ -0,0 +1,20 @@ +# Optimal student---topic assignment + +The script `assignment.py input.toml` calculates **all** optimal student---topic assignments under the assumption +that the $i$-th topic preference of student $v$ is worth $\approx 2^{-i}$. Then we set up an ILP that maximizes the +score over all students, adds cutting planes to enumerate all optimal solutions and draws one at random from them. + +It is possible to set a seed in the code to ensure the reproducibility of the procedure. + +First steps: +``` +pip install -r requirements.txt +``` + +Then: `python assignment.py input.toml`, where `input.toml` has the following format: +``` +[students] +a=[1,2,3] +b=[2,4] +``` +Here, we have two students `a` and `b`. Student `a` would prefer topic `1` over topic `2` over topic `3`, while student `b` would prefer topic `2` over topic `4`. diff --git a/assignment.py b/assignment.py new file mode 100755 index 0000000..61f7d62 --- /dev/null +++ b/assignment.py @@ -0,0 +1,145 @@ +#!/bin/python +import glpk +import os +import re +import toml +import sys +import math +import random + +random.seed(1409) +# 1 input parameter, the input filename + +if len(sys.argv) < 2: + print("Usage: assignment.py <configuration.toml>") + sys.exit(-1) + +with open(sys.argv[1]) as f: + tm = toml.load(f) + +if not ("students" in tm): + print(f"Missing table students with preferences in {sys.argv[1]}, e.g.\n[students]\n# Student a@abc.de preferes topic 2 over 6 over 4.\n\"a@abc.de\": [2,6,4]") + sys.exit(-1) + +students = tm['students'] +print("#Students = ",len(students)) +m = 0 +mlen = 0 +for s in students.keys(): + m = max(m,max(students[s])+1) + mlen = max(mlen, len(students[s])-1) + +topics = [x for x in range(0,m)] + +interest_decay = lambda x,y: x/math.pow(2,y) +factor = math.pow(2,mlen) +function="exponential" +if "settings" in tm: + if "interest_decay" in tm["settings"]: + if tm["settings"]["interest_decay"] == "lin": + interest_decay = lambda x,y: x-y + factor = mlen+1 + function="linear" + + +lp = glpk.LPX() +lp.name = 'assignment' +lp.obj.maximize = True +lp.rows.add(len(students)+len(topics)) +objective=[] +constraints=[] +for idx,(s,r) in enumerate(zip(students.keys(),lp.rows[:len(students)])): + r.name = 'student %s' % s + # Each student gets exactly one topic + r.bounds = 1.0,1.0 + last = 0 + beg = 0 + while beg<idx*len(topics): + constraints.append(0.0) + beg+=1 + comp = [(idx,val) for idx,val in enumerate(students[s])] + comp = sorted(comp, key=lambda x: x[1]) + for (dv,k) in comp: + while last < k: + objective.append(0.0) + constraints.append(0.0) + last+=1 + objective.append(interest_decay(factor, dv)) + constraints.append(1.0) + last+=1 + while last < len(topics): + objective.append(0.0) + constraints.append(0.0) + last+=1 + beg = (idx+1)*len(topics) + while beg < len(students)*len(topics): + constraints.append(0.0) + beg+=1 + +for e,r in enumerate(lp.rows[len(students):]): + r.name = 'topic %s' % e + # subject must be chosen at most 1 time. + r.bounds = 0.0,1.0 + beg = 0 + while beg < len(students)*len(topics): + if beg%len(topics) == e: + constraints.append(1.0) + else: + constraints.append(0.0) + beg+=1 +lp.cols.add(len(students)*len(topics)) +for c in lp.cols: + c.name = 'x_%d_%d' % (c.index//len(topics),c.index%len(topics)) + c.bounds = 0.0, 1.0 +lp.obj[:] = objective +iteration = 0 +optimal_solutions = [] +best_solution = 0 +while True: + lp.matrix = constraints + retval = lp.simplex() + assert retval is None + if lp.status != 'opt': + break + for col in lp.cols: + col.kind = int + + retval = lp.integer() + + assert retval is None + + if lp.status != 'opt': + break + if lp.obj.value < best_solution: + break + else: + best_solution = lp.obj.value + next_constraint = [] + current_solution = [] + for c in lp.cols: + if c.primal == 1: + first = c.name.find("_") + end = c.name.find("_", first+1) + idx = int(c.name[first+1:end]) + next_constraint.append(1.0) + current_solution.append((list(students.keys())[idx], c.name[end+1:])) + else: + next_constraint.append(0.0) + lp.rows.add(1) + r = lp.rows[-1] + r.name = 'exclude %s' % iteration + r.bounds = 0.0,len(students)-1 + iteration+=1 + # Add cutting plane + constraints.extend(next_constraint) + optimal_solutions.append(current_solution) + +if len(optimal_solutions) == 0: + print("Unsolvable assignment!") + sys.exit(-1) +print("#Optimal Solutions = {0}; objective weight = {1:.6}; {2} scoring".format(len(optimal_solutions), best_solution, function)) +print("Uniform choice among optimal solutions:") +opt = random.choice(optimal_solutions) +for (stud,choice) in opt: + print("{0:<40} Topic {1}".format(stud, choice)) + diff --git a/input.toml b/input.toml new file mode 100644 index 0000000..066c2d6 --- /dev/null +++ b/input.toml @@ -0,0 +1,16 @@ +[students] +"A" = [13,8,7] +"B" = [6,3,1] +"C" = [1,4,6] +"D" = [4,6,1] +"E" = [1,11,15] +"F" = [1,6,9] +"G" = [1,4,8] +"H" = [6,11,13] +"I" = [5,7,11] +"J" = [9,10,11] +"K" = [4,6,1] + +[settings] +# Either lin or exp for linear or exponential decay +interest_decay='exp' diff --git a/requirements.txt b/requirements.txt new file mode 100644 index 0000000..e4574dc --- /dev/null +++ b/requirements.txt @@ -0,0 +1,2 @@ +toml==0.10.2 +glpk==0.4.8 |