Scheduling group presentations with Sage

A blog post describing what I'm doing here

# Reading in the data

(If you wanted to run this with the same data you would need to copy the following file to your project also: 2015-2016-availability.csv.)

import csv
f=open('2015-2016-availability.csv','r')
raw_data = [row for row in csv.reader(f)]
f.close()

Grabbing the company names

companylabels = [row[0] for row in raw_data[1:]]
companylabels

['Whetstone Industries', 'Instant', 'Cardiff Calculus Crew', 'MathsFC.co.uk', 'Efficient', 'Alpha(2)', 'Compitance with a capital Q', 'Ambrosia', 'Ridgway Ltd.', 'Delta', 'Honeybadger', 'The Squadratics', 'PiMaticians', 'Easy Alpha Mathematics', 'Enwaduron', 'Prime co.', 'Pixel', 'Mathletico Madrid', 'Tech.ED', 'Mathemagicians', 'Bearded Muffins', 'Panda and Co', 'QED Solutions', 'Timekeeper', 'Awesome Arithmetic', 'SOUVLAKI', 'Alpha(1)', 'The Encyclopaedophiles', 'CompConnect', 'E=MCHammer', 'ATAK', 'Mathematician Masters', 'HANJ Developments', 'Supremum', 'BudgEat']

Checking that have correct amount

len(companylabels)

35

Grabbing the schedule labels

schedulelabels = [s.strip() for s in raw_data[0][1:]]
schedulelabels
len(schedulelabels)

['MON0900', 'MON0930', 'MON1000', 'MON1030', 'MON1100', 'MON1130', 'MON1200', 'MON1230', 'MON1300', 'MON1330', 'MON1400', 'MON1430', 'MON1500', 'MON1530', 'MON1600', 'MON1630', 'MON1700', 'MON1730', 'TUE0900', 'TUE0930', 'TUE1000', 'TUE1030', 'TUE1100', 'TUE1130', 'TUE1200', 'TUE1230', 'TUE1300', 'TUE1330', 'TUE1400', 'TUE1430', 'TUE1500', 'TUE1530', 'TUE1600', 'TUE1630', 'TUE1700', 'TUE1730', 'THU0900', 'THU0930', 'THU1200', 'THU1230', 'THU1300', 'THU1330', 'THU1400', 'THU1430', 'THU1500', 'THU1530', 'THU1600', 'THU1630', 'THU1700', 'THU1730', 'FRI1000', 'FRI1030', 'FRI1100', 'FRI1130', 'FRI1200', 'FRI1230', 'FRI1300', 'FRI1330', 'FRI1400', 'FRI1430', 'FRI1500', 'FRI1530', 'FRI1600', 'FRI1630', 'FRI1700', 'FRI1730']
66

Cleaning the data from doodle

def clean(l):
    if l == '':
        return 0
    return 1
data = [[clean(l) for l in row[1:]] for row in raw_data[1:]]

Double checking that have not lost any data

M = matrix(data) # Converting data to a matrix
M.dimensions() == (len(companylabels), len(schedulelabels))

False

Removing schedule slots with no entries

indices = [i for i, x in enumerate([max(row) for row in M.transpose()]) if x == 0]
schedulelabels = [s for i,s in enumerate(schedulelabels) if i not in indices]
len(schedulelabels)

57

Plotting the graph that defines our problem

M = matrix([row for row in M.transpose() if max(row) != 0]).transpose() # Removing unconnected time slots (removing columns with 0 values)
g= BipartiteGraph(M) # Creating a graph
p = g.coloring()  # Obtaining a coloring of the graph (as graph is bi partite this gets companies in one colour and slots in another
g.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p,svg=False) # Draw the graph

# Solve the problem

Solve the maximum matching algorithm associated with our bi-partite graph (in essence this pairs schedules and companies in such a way as to maximise the number of pairings). Code lifted from Sage documentation: http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#matching

p = MixedIntegerLinearProgram()
matching = p.new_variable(binary=True)
p.set_objective(sum(matching[e] for e in g.edges(labels=False)))
for v in g:
      p.add_constraint(sum(matching[e]
          for e in g.edges_incident(v, labels=False)) <= 1)
p.solve()
matching = p.get_values(matching)
schedule = [e for e,b in matching.iteritems() if b == 1]

34.0

# Plotting the solution to our problem

B=Graph(schedule)
p = B.coloring()
B.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p,svg=False)

Viewing the schedule

schedule = sorted([sorted(s) for s in schedule])
schedule  # Printing out the schedule in 'unfriendly' form

[[4, 78], [5, 74], [13, 57], [14, 59], [17, 60], [18, 72], [20, 65], [21, 71], [23, 67], [24, 68], [25, 58], [26, 70], [29, 75], [30, 77], [32, 80], [33, 66], [34, 84], [36, 69], [38, 63], [40, 79], [41, 85], [42, 86], [43, 62], [44, 73], [46, 61], [48, 64], [49, 76], [50, 83], [51, 81], [52, 87], [53, 88], [54, 82], [55, 89], [56, 90]]

# Printing it out in a more readable way
for s in sorted([companylabels[s[1] - len(schedulelabels)]+ ": " + schedulelabels[(s[0])]  for s in schedule]):
    print s

ATAK: FRI1530
Alpha(1): FRI1430
Alpha(2): FRI1100
Ambrosia: FRI1330
Awesome Arithmetic: FRI1500
Bearded Muffins: THU1230
Cardiff Calculus Crew: TUE1000
CompConnect: FRI1000
Compitance with a capital Q: THU1630
Delta: THU1400
E=MCHammer: FRI1030
Easy Alpha Mathematics: TUE1730
Efficient: FRI1230
Enwaduron: TUE1400
HANJ Developments: FRI1700
Honeybadger: TUE1500
Instant: TUE1700
Mathemagicians: FRI1400
Mathematician Masters: FRI1600
Mathletico Madrid: MON1330
MathsFC.co.uk: TUE1130
Panda and Co: MON1300
PiMaticians: THU1530
Pixel: FRI1130
Prime co.: TUE1230
QED Solutions: THU1730
Ridgway Ltd.: TUE1330
SOUVLAKI: FRI1630
Supremum: FRI1730
Tech.ED: THU1200
The Encyclopaedophiles: THU1430
The Squadratics: TUE1530
Timekeeper: THU1330
Whetstone Industries: MON1730

# Printing it out in a more readable way
for s in sorted([schedulelabels[(s[0])] + ": " + companylabels[s[1] - len(schedulelabels)]  for s in schedule]):
    print s

FRI1000: CompConnect
FRI1030: E=MCHammer
FRI1100: Alpha(2)
FRI1130: Pixel
FRI1230: Efficient
FRI1330: Ambrosia
FRI1400: Mathemagicians
FRI1430: Alpha(1)
FRI1500: Awesome Arithmetic
FRI1530: ATAK
FRI1600: Mathematician Masters
FRI1630: SOUVLAKI
FRI1700: HANJ Developments
FRI1730: Supremum
MON1300: Panda and Co
MON1330: Mathletico Madrid
MON1730: Whetstone Industries
THU1200: Tech.ED
THU1230: Bearded Muffins
THU1330: Timekeeper
THU1400: Delta
THU1430: The Encyclopaedophiles
THU1530: PiMaticians
THU1630: Compitance with a capital Q
THU1730: QED Solutions
TUE1000: Cardiff Calculus Crew
TUE1130: MathsFC.co.uk
TUE1230: Prime co.
TUE1330: Ridgway Ltd.
TUE1400: Enwaduron
TUE1500: Honeybadger
TUE1530: The Squadratics
TUE1700: Instant
TUE1730: Easy Alpha Mathematics