College admissions with ties and common quotas: Integer programming approach
College admissions with ties and common quotas: Integer programming approach
复制标题
具有联系和共同配额的大学招生：整数规划方法
DOI：
10.1016/j.ejor.2021.08.033
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zsuzsanna Jank
中科院分区：
文献类型：
--
作者：
K. Ágoston;P. Biró;Endre Kováts;Zsuzsanna Jank
匈牙利的大学入学是通过集中计划组织的。在本文中，我们研究了该应用程序的两个主要特点：关系和通用配额。当一些学生在某个课程中得分相同时，就会出现平局。如果项目中最后一组申请者没有足够的席位，那么在实践中会使用三种合理的政策：1）所有学生都必须被拒绝，如在匈牙利；2）所有学生都可以被接受，如在智利；3）通过抽签决定哪些学生可以从该组中被录取，如在爱尔兰。尽管可以针对上述三种情况中的每一种情况有效地计算学生最优稳定匹配，但我们开发了（混合）整数规划（IP）公式来解决这些问题，并比较了 2008 年匈牙利应用的真实实例中三种政策获得的解决方案。就匈牙利而言，共同配额来自于其项目所施加的教师配额以及为每个学科的国家资助学生设定的国家配额。公共配额的重叠结构使得寻找稳定解决方案的计算问题成为NP难题，即使对于严格的排名也是如此。在联系和共同配额的情况下，我们为匈牙利和智利的政策提出了两个合理稳定的解决方案。我们开发了（混合）IP 公式来解决这些稳定匹配问题，并在 2008 年和 2009 年的大规模实际实例上在两种不同的假设下测试了它们的性能。我们证明，最常见的情况在实践中也可以通过 IP 技术解决。
Admission to universities is organised in a centralised scheme in Hungary. In this paper we investigate two major specialities of this application: ties and common quotas. A tie occur when some students have the same score at a programme. If not enough seats are available for the last tied group of applicants at a programme then there are three reasonable policies used in practice: 1) all must be rejected, as in Hungary 2) all can be accepted, as in Chile 3) a lottery decides which students are accepted from this group, as in Ireland. Even though student-optimal stable matchings can be computed efficiently for each of the above three cases, we developed (mixed) integer programming (IP) formulations for solving these problems, and compared the solutions obtained by the three policies for a real instance of the Hungarian application from 2008. In the case of Hungary common quotas arise from the faculty quotas imposed on their programmes and from the national quotas set for state-financed students in each subject. The overlapping structure of common quotas makes the computational problem of finding a stable solution NP-hard, even for strict rankings. In the case of ties and common quotas we propose two reasonable stable solution concepts for the Hungarian and Chilean policies. We developed (mixed) IP formulations for solving these stable matching problems and tested their performance on the large scale real instance from 2008 and also for one from 2009 under two different assumptions. We demonstrate that the most general case is also solvable in practice by IP technique.
DOI：
10.1007/978-3-319-07959-2_2
发表时间：
2013-08
期刊：
ArXiv
影响因子：
--
作者：
P. Biró;D. Manlove;Iain McBride
通讯作者：
P. Biró;D. Manlove;Iain McBride
具有比例约束的稳定匹配
影响因子：
2.7
作者：
Nguyen, Thành;Vohra, Rakesh
通讯作者：
Vohra, Rakesh