# Allocating Students to Industry Placements Using Integer Programming and Ant Colony Optimisation
## 2 Previous Work  
The problem of finding _matchings_ commonly occurs in a number of real-world situations [6]. The basic idea underlying the problem is to identify pairings between objects in any two given sets. [PERSON]'s marriage problem [10] is a classic matching problem, where given a set of men and a set of women, the task is to maximise the number of pairs of men and women that can be'married'. Similarly, a number of allocation problems include those where students need to be allocated to colleges [11] or projects [12], residents allocated to hospitals [11; 13], and roommates allocated to rooms [14]. In this paper, we consider allocations of students to placements, and so without loss of generality will refer to the two sets as'students' and 'placements'. In many cases, the set of students and (or) the set of placements have a list of preferred partners in the corresponding set. This is referred to as _matching under preferences_ (e.g., see [6]). Preferences can be two-sided or, alternatively, only one set may have preferences. Preferences are not given to every member of the set, and a member's preference can be totally or partially ordered. For example, a placement may prefer student \(s_{1}\) over \(s_{2}\), but be indifferent between possible matchings with students \(s_{1}\) and \(s_{3}\). This gives rise to problems such as the stable matching problem (a matching is _stable_ if there are no two pairs in the matching, say \((s_{1},p_{1})\) and \((s_{2},p_{2})\), where \(s_{1}\) prefers \(p_{2}\) to \(p_{1}\) and \(s_{2}\) prefers \(p_{1}\) to \(p_{2}\)) with partially ordered and incomplete lists (SMPI) and the hospital/residents problem with partially ordered lists (HRP) [15]. In many of these cases, the problem is NP-hard (e.g., [15]). [PERSON] defines three types of stable matchings [16]. A _weak stable matching_ is one where there are no pairs, \((s_{1},p_{1})\) and \((s_{2},p_{2})\), in the matching such that \(s_{1}\) prefers \(p_{2}\) to \(p_{1}\) and \(s_{2}\) prefers \(p_{1}\) to \(p_{2}\). Strong stability occurs where, for any two pairs \((s_{i},\,p_{i})\), \(i=1,2\), student \(s_{1}\) strictly prefers their own partner to \(p_{2}\) and \(s_{2}\) either strictly prefers \(p_{2}\) to \(p_{1}\) or equally prefers both \(p_{1}\) and \(p_{2}\). (Note: in this case at most one of the two pairs can hold an equal preference.) Super-stability occurs where, for any two pairs \((s_{i},\,p_{i})\), \(i=1,2\), each \(s_{i}\) strictly prefers their own partner to the other's partner. [PERSON] and [PERSON] [17] discuss the case where there are ties in the preference lists which may also be incomplete. In this case, finding a maximum weakly stable matching is NP-hard. According to the findings of [16; 17], the WIL problem is similar to a strong stable matching problem with ties in the preference lists and incomplete preference lists, and hence it is an NP-hard problem. Several types of matching, assignment and allocation problems have been solved with IPs [18; 19; 20; 21]. [PERSON] et al. [18] provide an overview of matching under preferences and thoroughly review the literature in the area. [PERSON] [19] develops an embellished transportation IP model to find a matching between wineries to distributors. In at least one example, the model proposed a matching that resulted in a long-term partnership. [PERSON] and [PERSON] [20] examine the problem of assigning employees to 86 different gas stations distributed around Kuwait. They consider a multi-stage mixed integer programming approach, where in the first stage employees are assigned to stations and in the second stage individual shifts for the employees are determined. [PERSON] et al. [21] consider the problem of online resource allocation in a grid environment. They use a linear programming approach, which is able to efficiently find new solutions when new information is available. Ref.