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}$$