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 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}\]
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.