  Motivated by the shortage of seats that the Chilean school choice system is
facing, we introduce the problem of jointly increasing school capacities and
finding a student-optimal assignment in the expanded market. Due to the
theoretical and practical complexity of the problem, we provide a comprehensive
set of tools to solve the problem, including different mathematical programming
formulations, a cutting plane algorithm, and two heuristics that allow
obtaining near-optimal solutions quickly. On the theoretical side, we show the
correctness of our formulations, different properties of the objective and
feasible region that facilitate computation, and also several properties of the
underlying mechanism to find a student-optimal matching under capacity
expansions. On the computational side, we use data from the Chilean school
choice system to demonstrate the impact of our framework and derive insights
that could help alleviate the problem. Our results show that each additional
seat can benefit multiple students and that we can effectively target the
assignment of previously unassigned students or improve the assignment of
several students through improvement chains. Nevertheless, our results show
that the marginal effect of each additional seat is decreasing and that simply
adding seats is insufficient to ensure every student gets assigned to some
school. Finally, we discuss several extensions of our framework, showcasing its
flexibility to accommodate different needs.
