Project allocation optimisation Code

Question

I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.

Variables

$X_{i,j}$ = 1, if student i is allocated to project j and 0, otherwise

$C_{i,j}$ can take any value in set C where,C ∈ [1,2,3]

Constraints

$\sum_{j=1}^{Tp} X_{i,j} = 1$

Each student is allocated to one project where Tp = total projects

$\sum_{i=1}^{Ts} X_{i,j} = 1$

Each project is allocated to one student where Ts = total students

$\sum_{j=1}^{Tp} C_{i,j} \times X_{i,j} \geq 1$

Each student is allocated a project that is one of their preferences

Objective Function

Minimize $\sum_{i=1}^{Ts}\sum_{j=1}^{Tp} C_{i,j} \times X_{i,j}$

To minimize the sum of the rankings.

How can I code this integer optimisation problem in MATLAB or another way?

Thank you!!

Answer 1

First, a comment: I don't see the purpose of the third constraint ($\sum_{j=1}^{T_p} C_{i,j} X_{i,j} \ge 1$). Since $C_{i,j}\ge 1$, this constraint is implied by the first one (assign every student to a project).

Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.

Answer 2

I agree with @prubin in both statements. There is no need for the third constraint and Excel + Solver may solve your problem.

In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/

Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.

It can even have some interactive tools (forms, interface with spreadsheets, etc.).

An short example with your code: https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M

An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).