# Allocating Students to Industry Placements Using Integer Programming and Ant Colony Optimisation
## 4 Integer Programming Model  
A preliminary IP model is created for the IBLP, which is defined as follows. We define binary variables \(x\) for allocating students to companies as follows: \(x_{sc}=1\) if student \(s\) is allocated to company \(c\). Additionally, binary variables \(y\) are defined for counting purposes. Let \(A_{c}\) be the number of students allocated to company \(c\). The vector \(y_{c}\) gives a unary representation of \(A_{c}\). Here, \(y_{ck}=1\) if \(k\leq A_{c}\) and 0 otherwise. The length of this unary vector is modulo \(|S|=n\) for every company. For example, \(y_{c}=[1,1,1,0,0]\) would represent three students allocated to company \(c\) from a total of \(|S|=5\) students available. This representation enables an efficient way to evenly distribute students among companies when there are insufficient students to fill the placements. The details of the notation used for the model are summarised in Table 1.  
There are multiple components in the objective function of the problem associated with company preferences. The aim is to maximise the number of allocations at the same time whilst respecting gender equity. The IP model is as follows:  
Maximise \[\sum_{s\in S}\sum_{c\in\mathcal{C}}(\mathcal{L}-p_{sc})x_{sc}-\sum_{c\in \mathcal{C}}\sum_{k=1}^{n}v_{c}y_{ck}-\left(\sum_{c\in\mathcal{C}}\biggl{|}\sum _{s\in M}x_{sc}-\sum_{s\in F}x_{sc}\biggr{|}\right)\] (2) Subject to \[\sum_{c\in C}x_{sc}\leq 1 \forall s\in S\] (3) \[\sum_{s\in S}x_{sc}\leq r_{c} \forall c\in C\] (4) \[x_{sq}=0 \forall s\in S,\;\forall q\in Q_{s}\] (5) \[\sum_{s\in S}x_{sc}-\sum_{k=1}^{n}y_{ck}=0 \forall c\in C\] (6) \[y_{ck}-y_{c(k-1)}\leq 0 \forall c\in C,\;\forall k\in\{2,\ldots,n\}\] (7) \[x_{sc},y_{ck}\in\{0,1\}, \forall s\in S,\forall c\in C,\;\forall k\in\{1,\ldots,n\}\] (8)  
The problem is defined as a maximisation problem, which means the penalty terms are negated in the objective function. The first term in the objective sums the allocated preference values for each student \(s\) allocated to company \(c\) using the preference weights \(p_{sc}\). Here, a constant \(\mathcal{L}\) is used to ensure the objective values are positive valued. (In principle, \(\mathcal{L}\) is not required, though, positive values makes comparisons between the approaches more straightforward.) The second term includes a weight \(v_{c}=\sum\limits_{k=1}^{\mathcal{C}_{c}}k\), where \(r_{c}\) is the number of students requested by company \(c\), to give priority to companies requesting smaller number \begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Definition** \\ \hline
**Sets** & \\ \hline \(S\) & The set of \(n\) students \(S=\{s_{1},\ldots,s_{n}\}\) \\ \hline \(C\) & The set of \(m\) companies \(C=\{c_{1},\ldots,c_{m}\}\) \\ \hline \(B_{i}\) & The set \(B_{i}\subseteq\mathcal{C}\) of companies in sector \(i\in[1,b]\) \\ \hline \(Q\) & The set of sets of companies belonging to each of the sectors: \(Q=\{B_{1},B_{2},\ldots,B_{b}\}\) \\ \hline \(Q_{s}\) & The set of companies belonging to sectors where student \(s\) has been previously placed \\ \hline \(M\) & The set of male students \(M\subseteq S\) \\ \hline \(F\) & The set of female students \(F\subseteq S\) \\ \hline \multicolumn{2}{c}{**Parameters**} \\ \hline \(r_{c}\) & The number of available placements in company \(c\) \\ \hline \(R\) & The total number of placements available: \(R=\sum\limits_{c\in\mathcal{C}}r_{c}\) \\ \hline \(p_{sc}\) & \(p_{sc}\in\{1,2,3\}\) is the preference rating of student \(s\) by company \(c\) \\ \hline \(v_{c}\) & Constants which are used to prioritise companies with relatively low numbers of placements \\ \hline \multicolumn{2}{c}{**Variables**} \\ \hline \(x_{sc}\) & Binary variables where \(x_{sc}=1\) if student \(s\) is allocated to company \(c\) \\ \hline \(y_{c}\) & A vector of binary variables providing a uniary representation of the number of students \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The table of notations used in the IP model.