1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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))
|