I need to model the following problem:

In the next semester, the school plans to replace the tutorials by self-organized student groups. Your task is to find the best possible partition of students into groups and to appoint a group leader for each group. To achieve this task, you are given a list of students students. Each student needs to be assigned to exactly one group, and each group needs to have a (student) leader. Every student can be a leader, but we can have only one per group. A leader needs to be assigned to the group he is leading. The number of groups needs to be at least g and at most G. The quality of the groups depends on two criteria. First, the collaboration quality of a student i in a group with leader j is given by collaboration[i,j]. Furthermore, each student i has a certain leadership quality given by leadership[j]. You have to maximize the overall collaboration quality plus the sum of the leadership qualities of the leaders.

I have come up with the following and was wondering if I'm missing something or if someone can show me in the right direction:

I used the variable $x_{i,j}$ if a student $i$ is assigned to the group with leader $j$ ($x_{i,j}=1$) or not ($x_{i,j}=0$). The variable $y_j$ shall denote whether student $j$ is a leader ($=1$) or not ($=0$).

I assumed that there are $n$ students and $m$ leaders. Then I came up with the following LP:

max $\sum_{i=1}^n \sum_{j=1}^m x_{i,j} \cdot \text{collaboration}_{i,j} + \sum_{j=1}^m y_j \cdot \text{leadership}_j$


$\sum_{j=1}^m x_{i,j} = 1 \qquad \forall i \in \{1,\ldots,n\}$

$g \leq \sum_{j=1}^my_j \leq G$

$x_{i,j} \leq y_j \qquad \forall i \in \{1,\ldots,n\} \quad \forall j \in \{1,\ldots,m\}$

$x_{i,j} \in \{0,1\} \qquad \forall i \in \{1,\ldots,n\} \quad \forall j \in \{1,\ldots,m\}$

$y_j \in \{0,1\} \forall j \in \{1,\ldots,m\}$

This is as far as I have gotten. I know I'm missing the connection between $x_{i,j}$ and $y_{j}$. Also I'm not sure about my function I want to maximize. Help would be appreciated.

EDIT: After the comment I updated the constraints. We have a small example, where we can test our model and I'm not able to reproduce the correct anwser with the model above. Any suggetions, where my error is?

  • 1
    $\begingroup$ A student $i$ cannot be assigned to the group with leader $j$ if $j$ is not a leader, that is $x_{ij} \leq y_j$ $\endgroup$ – Marcello Sammarra Dec 4 '17 at 21:44

Your current model admits the possibility of a leader being assigned to another leader. You can eliminate this either by changing the first constraint to $\sum_j (x_{i,j} +y_i)=1$ (leaders are not assigned to anyone) or by adding the constraint $x_{i,i}=y_i\,\forall i$ (leaders, and only leaders, are assigned to themselves). If the collaboration value of assigning someone to herself is not 0, you should use the second approach to ensure proper credit in the objective function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.