I need to schedule 40ish talks and this needs to fit around the student availability as well as my own. In this post I'll describe how I did this using a combination of Doodle, +Sage Mathematical Software System and Graph Theory.
The beginning of this post will be some of the boring details but towards the end I start talking about the mathematics (so feel free to skip to there...).
First of all I needed to know my students availability.
For this I simply used Doodle: https://doodle.com. I kind of use Doodle for every meeting I have to schedule (they also offer a cool tool that lets you show your availability so students/colleagues have an indication of when I might be able to meet with them).
Here's a screenshot of the responses:
data = [[int(j) for j in row] for row in csv.reader(f)]
M = Matrix(data)
I then need to remove any particular scheduled slots that are not picked by any company:
M = matrix([row for row in M.transpose() if max(row) != 0]).transpose()
Once I've done this I can define the bi-partite graph (bi-partite simply means that the vertices can be separated in to 2 non adjacent collections):
g = BipartiteGraph(M)
p = g.coloring()
g.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)
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:
for e in g.edges_incident(v, labels=False)) <= 1)
schedule = [e for e,b in matching.iteritems() if b == 1]
(25, 47), (24, 53), (6, 46), (3, 64), (39, 67), (17, 69), (22, 55), (13,
48), (33, 41), (10, 63), (21, 61), (30, 52), (29, 65), (37, 70), (15,
54), (19, 51), (11, 59)]
p = B.coloring()
B.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)