Consider a situation where an instructor wishes to divide students into groups. Each group will be allocated a topic \(t\), from a pool of topics \(1,\ldots,T\). It is possible that each topic \(t\) is repeated a certain number of times across the class. Suppose that the maximum number of repetitions of a topic is \(r_{max}\). In total, there are \(N\) students in the class.
Suppose that students form their own groups, which they submit through a survey form. In total there are \(G\) such self-formed groups; each student appears in exactly 1 group.
In addition, we have the following information about each student:
This model allows you to maximise the diversity within a group and minimise the difference in skill within groups.
The overall objective function can be written as:
\[ \max \quad w_1 \left( \sum_{i=1}^{N-1} \sum_{j=i+1}^N \sum_{t=1}^T \sum_{r=1}^{r_{max}} z_{ijtr} \cdot d_{ij} \right) + w_2 (s_{min} - s_{max}) \]
where \(w_1\) and \(w_2\) are weights. They indicate which half of the objective function should be given priority.
First, let us introduce the decision variable of interest:
\[\begin{equation} x_{gtr} = \begin{cases} 1 & \text{if group $g$ is assigned to repetition $r$ of topic $t$} \\ 0 & \text{otherwise} \end{cases} \end{equation}\]
\(s_{min}\) and \(s_{max}\) are also decision variables. The objective function attempts to minimise the difference between them, ensuring all groups have a similar range of total skill.
This first constraint represents the need for each group to be assigned to exactly one topic-repetition combination:
\[ \sum_{t=1}^T \sum_{r=1}^{r_{max}} x_{gtr} = 1, \quad \forall g \]
\(z_{ijtr}\) is a binary variable, used to pick up whether the pairwise dissimilarity between student \(i\) and student \(j\) should be included in the objective function calculation.
\[\begin{eqnarray} z_{ijtr} &\le& \sum_{g=1}^G m_{ig} \cdot x_{gtr}, \quad \forall i,j,t,r \\ z_{ijtr} &\le& \sum_{g=1}^G m_{jg} \cdot x_{gtr}, \quad \forall i,j,t,r \\ z_{ijtr} &\ge& \sum_{g=1}^G m_{ig} \cdot x_{gtr} + \sum_{g=1}^G m_{jg} \cdot x_{gtr} - 1, \quad \forall i,j,t,r \end{eqnarray}\]
This set of constraints serve to regulate the total number of repetitions for each topic. \(r_{min}\) and \(r_{max}\) are input variables that the instructor needs to set.
\[\begin{eqnarray} a_{tr} &\ge& x_{gtr},\quad \forall t,r \\ a_{tr} &\le& \sum_{g=1}^G x_{gtr},\quad \forall t,r \\ \sum_{r=1}^{r_{max}} a_{tr} &\ge& r_{min},\quad \forall t \\ \sum_{r=1}^{r_{max}} a_{tr} &\le& r_{max},\quad \forall t \end{eqnarray}\]
Take note that the last constraint is automatically satisfied since {a_{tr}} is binary.
A similar set of constraints are used to bound the number of students in each eventually assigned group. \(n_{min}\) and \(n_{max}\) are also input variables; they dictate the bounds on the number of students in each assigned group.
\[\begin{eqnarray} \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} &\ge& a_{tr} \cdot n_{min}, \quad \forall t,r \\ \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} &\le& a_{tr} \cdot n_{max}, \quad \forall t,r \end{eqnarray}\]
We aim to maintain the skill level within each active group using the following constraints. Let \(M=\sum_{i=1}^N s_i\).
\[\begin{eqnarray} \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} \cdot s_i + M(1-a_{tr}) &\ge& s_{min}, \quad \forall t,r \\ \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} \cdot s_i &\le& s_{max}, \quad \forall t,r \\ \end{eqnarray}\]
When \(a_{tr}=1\), the lower bound applies to the total skill in that active topic-repetition combination. When \(a_{tr}=0\), the Big-M term relaxes the lower bound so inactive combinations do not force \(s_{min}\) to zero.
\[\begin{eqnarray} x_{gtr} &\in& \{0,1\} \\ a_{tr} &\in& \{0,1\} \\ s_{min} &\ge& 0 \\ s_{max} &\ge& 0 \end{eqnarray}\]