---
title: "Maximising Preference"
output: 
  rmarkdown::html_vignette:
    toc: true
    toc_depth: 2
vignette: >
  %\VignetteIndexEntry{Maximising Preference}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

# 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 (at most
$r_{max}$ 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_{max}} 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_{max}} 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}$ 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_{max}\}$.

\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_{max}} a_{tr} = \sum_{r=1}^{r_{max}} 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_{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_{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}
