Stable Marriage of Students

Starting Date: Anytime
Duration: 100 hours
Time commitment: To suit. Not end July or early August.
Prerequisites: Proficient programmer. Good at Maths

Constraint Satisfaction and the final year projects system

Prof Cohen is a world leading researcher in the theory and practice of constraints and has written some tools for the department that need to be improved.


At Royal Holloway, we allocate students to projects and staff as supervisors of those projects using a semi-automated process, using a C++ library called Lemon that solves the problem as a network flow optimization.  This is fine except that it does not work if students have different workloads (MSc, half unit etc.,)

The project would implement a solution either using a Valued Constraint Solver (see https://en.wikipedia.org/wiki/Constraint_programming, or http://www7.inra.fr/mia/T/toulbar2/), an optimizer (see https://developers.google.com/optimization/) or a direct algorithm such as min cost max flow (see https://en.wikipedia.org/wiki/Minimum-cost_flow_problem).

The process will use the generated (text) files from the online bidding process that both students and staff engage in to describe their preferences.

Similar (AI) systems are used worldwide to allocate doctors to training hospitals, children to schools etc.,

A good solution that compared the validity of the different techniques  would lead to a publication at the International Conference on Constraints.


Another program using the same technology that we require will allocate final year project students to their demo times.  Each student has a supervisor and a second marker and both must attend the demo.  However, each staff member should attend at most two demo sessions.  At present this is solved using the minizinc language (http://www.minizinc.org/) and  different solvers.  Different state-of-the-art solvers give enormously different solution times (from seconds to weeks)

Your job would be to automate the system and compare different solvers including gecode, Google Tool and Chuffed, and different models (formulations of the problem).

Ideally you would be able to explain the differences.

Similar (AI) problems need to be solved in factory workshop scheduling, fair experimental design etc.,

A good solution that compared the validity of the different techniques  would lead to a publication at the International Conference on Constraints.


I will teach the required theory to you.  You will code.  You will begin with my (working) code.