# Modeling Integer LP

I need to model the following problem:

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$

s.t.

$\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?

• 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$ – 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.