How to solve an optimization problems of this kind?

76 Views Asked by At

I have to solve a real-world optimization problem. I am teaching 33 students, a university lesson, and I am attempting to assign them 11 semester projects, based on their preference. I grouped them in 11 teams of 3 students per team, and asked them to state their 3 most preferenced projects.

Let student groups be $X_i , \text{where } i \in [1,11]$ and semester projects be $Y_i , \text{where } i \in [1,11]$

$X_1 \text{ chose in order of priority the projects } Y_7, Y_1, Y_10$
$X_2 \text{ chose in order of priority the projects } Y_2, Y_7, Y_6$
$... etc ...$

For simplicity's shake I will map this onto a matrix (columns = assignments, rows = groups, values = preferences)

\begin{matrix} 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 0\\ 0 & 1 & 0 & 0 & 0 & 3 & 2 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0 & 3 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 3 & 2 & 0 & 0 & 0 & 0\\ 3 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 2 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 2\\ 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 3 & 0 & 1 & 2 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 2 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 3 & 0 & 0 & 0 & 0 & 2\\ \end{matrix}


This is an integer programming problem (I think?). How can this problem be solved? Is there an algorithm for that kind of optimization problems? I am missing knowledge here.

1

There are 1 best solutions below

1
On BEST ANSWER

Take a look at the (balanced) assignment problem, which is what you probably have here (assuming you choose a suitable objective function, per LinAlg's comment).