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.

Maximising Preference

Model introduction

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\). However, each project team assigned to topic would comprise \(B\) sub-groups or sub-teams. Thus, in essence, there would be \(BT\) topics to be assigned to student groups. It is also possible that each topic \(t\) is repeated \(R_t\) times across the class. Note that the more common case, where there is only one sub-group per topic, can be easily attained by setting \(B=1\).

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. We let \(n_g\) represent the number of students in group \(g\), where \(g\) runs from \(1,\ldots,G\).

Finally, suppose we also have the preference that each self-formed group has for a particular topic \(t\), where \(t \in \{1, \ldots, BT \}\).

This model allows you to maximise the preference scores for each group.

Objective function

\[ \max \sum_{g=1}^G \sum_{t=1}^{BT} \sum_{r=1}^{R_t} x_{gtr} \cdot n_g \cdot p_{tg} \]

where \(p_{tg}\) corresponds to the preference score that group \(g\) has for topic \(t\). Since our objective function is formulated as a maximum, the preference scores should be coded such that higher scores indicate stronger preference for a topic.

The decision variable \(x_{gtr}\) is a binary variable.

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

Constraints

Group to topic-repetition combination

The first constraint ensures that each group is assigned to exactly one topic \(t\), where \(t \in \{1, \; \ldots, \; BT \}\).

\[ \sum_{t=1}^{BT} \sum_{r=1}^{R_t} x_{gtr} = 1, \quad \forall g \]

Number of repetitions per topic

This set of constraints serve to regulate the total number of repetitions for each topic. \(r_{min}\) and \(r_{max} = R_t\) are input variables that the instructor needs to set.

\(a_{tr}\) is a binary decision variable which indicates if repetition \(r\) of topic \(t\) is “live”, where \(r \in \{1 , \ldots, R_t\}\).

\[\begin{eqnarray} a_{tr} &\ge& x_{gtr}, \quad \forall t \in \{1,2,\ldots,BT \},\;r \\ a_{tr} &\le& \sum_{g=1}^G x_{gtr}, \quad \forall t \in \{1,2,\ldots,BT \},\;r \\ a_{tr} &\ge& r_{min}, \quad \forall t \in \{1,2,\ldots,T \} \end{eqnarray}\]

Balanced number of subgroups

The next constraint ensures that there is an equal number of subgroups for each “live” repetition of a topic. \[ \sum_{r=1}^{R} a_{tr} = \sum_{r=1}^R a_{(bT+t)r}, \quad \forall t \in \{1,2,\ldots,T \},\; \min(1,B-1)\le b \le \max(0, B-1) \]

This is where we can see that the ordering of all sub-groups in the preference matrix should be as follows:

\[ T_1S_1,\; T_2S_1,\; \ldots, \; T_1S_2, T_2S_2, \; \ldots T_TS_B \]

Number of students per subgroup

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_{tr}^{min}, \quad \forall t \in \{1,2,\ldots,BT \},\;r \\ \sum_{i=1}^N \sum_{g=1}^G m_{ig} \cdot x_{gtr} &\le& a_{tr} \cdot n_{tr}^{max}, \quad \forall t \in \{1,2,\ldots,BT \},\;r \end{eqnarray}\]

Binary and non-negativity constraints

Finally, as stated above, we have the following constraints on the decision variables.

\[\begin{eqnarray} x_{gtr} &\in& \{0,1\} \\ a_{tr} &\in& \{0,1\} \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.