The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]dogado.de.
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 \(R_t\) times across the class. 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\) 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_t} 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_t} 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_t} a_{tr} &\ge& r_{min},\quad \forall t \\ \sum_{r=1}^{R_t} a_{tr} &\le& r_{max},\quad \forall t \end{eqnarray}\]
A similar set of constraints are used to bound the number of students in each eventually assigned group.
\[\begin{eqnarray} \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} &\ge& a_{tr} \cdot n^{min}_{tr}, \quad \forall t,r \\ \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} &\le& a_{tr} \cdot n^{max}_{tr}, \quad \forall t,r \end{eqnarray}\]
We aim to maintain the skill level within each group using the following constraints.
\[\begin{eqnarray} \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} \cdot s_i &\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}\]
\[\begin{eqnarray} x_{gtr} &\in& \{0,1\} \\ a_{tr} &\in& \{0,1\} \\ s_{min} &\ge& 0 \\ s_{max} &\ge& 0 \end{eqnarray}\]
These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.
Health stats visible at Monitor.