Integer programming formulations for college admissions with ties

Abstract

When two students with the same score are competing for the last slot at a university programme in a central admission scheme then different policies may apply across countries. In Ireland only one of these students is admitted by a lottery. In Chile both students are admitted by slightly violating the quota of the programme. Finally, in Hungary none of them is admitted, leaving one slot empty. We describe the solution by the Hungarian policy with various integer programing formulations and test them on a real data from 2008 with around 100,000 students. The simulations show that the usage of binary cutoff-score variables is the most efficient way to solve this problem when using IP technique. We also compare the solutions obtained on this problem instance by different admission policies. Although these solutions are possible to compute efficiently with simpler methods based on the Gale-Shapley algorithm, our result becomes relevant when additional constraints are implied or more complex goals are aimed, as it happens in Hungary where at least three other special features are present: lower quotas for the programmes, common quotas and paired applications for teachers studies.