In this work, we introduce the problem of jointly allocating a school capacity expansion (given a fixed budget) and finding the best allocation for the students in the expanded market. Given the computational complexity of the problem, we provide an integer quadratically-constrained programming formulation and study its linear reformulations. We also propose two heuristics: A greedy algorithm and an LP-based method. We empirically evaluate the performance of our approaches in a detailed computational study. We observe the practical superiority of the linearized model in comparison with its quadratic counterpart and we outline their computational limits. Finally, we use the Chilean school choice system data to empirically demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. In addition, depending on the decision-maker, our methodology can prioritize the assignment of previously unassigned students or improve the assignment of several students through improvement chains.
翻译:在这项工作中,我们提出了共同分配学校能力扩大(设定固定预算)和在扩大的市场中为学生找到最佳分配办法的问题。鉴于这一问题的计算复杂性,我们提供了全方位的受限制的编程配制和研究其线性重拟。我们还提出了两种累进主义:贪婪算法和基于LP的方法。我们在详细的计算研究中从经验上评估了我们方法的绩效。我们观察到线性模式与其四面形对应方相比的实际优势,我们概述了它们的计算限制。最后,我们利用智利学校选择系统的数据,从经验上展示了在稳定条件下能力规划的影响。我们的结果显示,每个新增的学校座位都可以使多名学生受益。此外,根据决策者的情况,我们的方法可以优先分配以前未分配的学生,或者通过改进链改进若干学生的分派。