Abstract
We consider the problem of allocating students to project topics satisfying side constraints and taking into account students’ preferences. Students rank projects according to their preferences for the topic and side constraints limit the possibilities to team up students in the project topics. The goal is to find assignments that are fair and that maximize the collective satisfaction. Moreover, we consider issues of stability and envy from the students’ viewpoint. This problem arises as a crucial activity in the organization of a first year course at the Faculty of Science of the University of Southern Denmark. We formalize the student-project allocation problem as a mixed integer linear programming problem and focus on different ways to model fairness and utilitarian principles. On the basis of real-world data, we compare empirically the quality of the allocations found by the different models and the computational effort to find solutions by means of a state-of-the-art commercial solver. We provide empirical evidence about the effects of these models on the distribution of the student assignments, which could be valuable input for policy makers in similar settings. Building on these results we propose novel combinations of the models that, for our case, attain feasible, stable, fair and collectively satisfactory solutions within a minute of computation. Since 2010, these solutions are used in practice at our institution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
In the student view, the partial function \(\sigma \) will be from S to \(P\) and it will indicate the project to which a single student \(s_q\in S\) is assigned or it will be undefined if \(s_q\) is not assigned to any project.
Birgitte H. Kallipolitis, Marianne Holmer, Paul C. Stein, Per Lyngs Hansen, Rolf Fagerberg and Søren Sten Hansen. Naturvidenskabeligt Projekt. Målsætning & Krav. 2008. Course document at the Faculty of Natural Science, University of Southern Denmark.
In the implementation, to avoid numerical problems, we used the weighting scheme (17) until 8 even for instances with \({\varDelta }>8\). Then, for values of \(h>8\) we set \(w_h=w_8+1\). It is not too hard to prove that using the distribution approach and \({\varDelta }\) in the definition of weights still yields the leximin solution. It will suffice here to show that in our experimental results the assignments we found had indeed the same value vectors as those of the leximin solutions.
We set a time limit of 3600 s per MILP problem but on instance 2015 (stable)-greedy_max had to solve 13 MILP problems.
Actually, a few students gave more than 7 preferences but this seems not to have an impact in our results.
References
Abdulkadirolu, A., Pathak, P. A., & Roth, A. E. (2009). Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5), 1954–78. https://doi.org/10.1257/aer.99.5.1954.
Abraham, D. J., Irving, R. W., & Manlove, D. F. (2007). Two algorithms for the student-project allocation problem. Journal of Discrete Algorithms, 5(1), 73–90. https://doi.org/10.1016/j.jda.2006.03.006.
Anwar, A. A., & Bahaj, A. (2003). Student project allocation using integer programming. IEEE Transactions on Education, 46(3), 359–367. https://doi.org/10.1109/TE.2003.811038.
Arulselvan, A., Cseh, Á., Groß, M., Manlove, D.F., & Matuschke, J. (2016). Matchings with lower quotas: Algorithms and complexity. CoRR arXiv:1412.0325. Preliminary version appeared at ISAAC 2015.
Ashlagi, I., & Shi, P. (2014). Improving community cohesion in school choice via correlated-lottery implementation. Working paper.
Atkinson, A. B. (1970). On the measurement of inequality. Journal of Economic Theory, 2(3), 244–263.
Bertsimas, D., Farias, V. F., & Trichakis, N. (2012). On the efficiency-fairness trade-off. Management Science, 58(12), 2234–2250. https://doi.org/10.1287/mnsc.1120.1549.
Biró, P., Fleiner, T., Irving, R. W., & Manlove, D. F. (2010). The college admissions problem with lower and common quotas. Theoretical Computer Science, 411(34), 3136–3153. https://doi.org/10.1016/j.tcs.2010.05.005.
Biró, P., & McDermid, E. (2014). Matching with sizes (or scheduling with processing set restrictions). Discrete Applied Mathematics, 164(Part 1), 61–67. https://doi.org/10.1016/j.dam.2011.11.003.
Bogomolnaia, A., & Moulin, H. (2001). A new solution to the random assignment problem. Journal of Economic Theory, 100(2), 295–328. https://doi.org/10.1006/jeth.2000.2710.
Bouveret, S., & Lang, J. (2008). Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. Journal of Artificial Intelligence Research, 32, 525–564. https://doi.org/10.1613/jair.2467.
Brams, S. J., & Taylor, A. D. (1996). Fair division: From cake-cutting to dispute resolution. Cambridge: Cambridge University Press.
Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061–1103. https://doi.org/10.1086/664613.
Budish, E., & Cantillon, E. (2012). The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. American Economic Review, 102(5), 2237–71. https://doi.org/10.1257/aer.102.5.2237.
Dye, J. (2001). A constraint logic programming approach to the stable marriage problem and its application to student-project allocation. In Proceedings of the sixth international workshop on computer-aided software engineering.
El-Atta, A., & Moussa, M.I. (2009). Student project allocation with preference lists over (student, project) pairs. In Second international conference on computer and electrical engineering, 2009. ICCEE ’09 (Vol. 1, pp. 375–379). https://doi.org/10.1109/ICCEE.2009.63.
Fragiadakis, D. E., & Troyan, P. (2014). Improving welfare in assignment problems: An experimental investigation. http://erl.tamu.edu/working-papers/. Working paper at Economic Research Laboratory, Texas A&M University.
Garg, N., Kavitha, T., Kumar, A., Mehlhorn, K., & Mestre, J. (2010). Assigning papers to referees. Algorithmica, 58(1), 119–136. https://doi.org/10.1007/s00453-009-9386-0.
Geiger, M. J., & Wenger, W. (2010). On the assignment of students to topics: A variable neighborhood search approach. Socio-Economic Planning Sciences, 44(1), 25–34. https://doi.org/10.1016/j.seps.2009.03.001.
Gusfield, D., & Irving, R. (1989). The stable marriage problem: Structure and algorithms. Cambridge: MIT Press.
Harper, P. R., de Senna, V., Vieira, I. T., & Shahani, A. K. (2005). A genetic algorithm for the project assignment problem. Computers & Operations Research, 32(5), 1255–1265. https://doi.org/10.1016/j.cor.2003.11.003.
Hooker, J. N., & Williams, H. P. (2012). Combining equity and utilitarianism in a mathematical programming model. Management Science, 58(9), 1682–1693. https://doi.org/10.1287/mnsc.1120.1515.
Iwama, K., & Miyazaki, S. (2008). A survey of the stable marriage problem and its variants. In International conference on informatics education and research for knowledge-circulating society (ICKS 2008) (pp. 131–136). https://doi.org/10.1109/ICKS.2008.7.
Iwama, K., Miyazaki, S., & Yanagisawa, H. (2012). Improved approximation bounds for the student-project allocation problem with preferences over projects. Journal of Discrete Algorithms, 13, 59–66. https://doi.org/10.1016/j.jda.2012.02.001.
Kagel, J. H., & Roth, A. E. (Eds.). (1997). The handbook of experimental economics. Princeton: Princeton University Press.
Lu, T., & Boutilier, C.E. (2012). Matching models for preference-sensitive group purchasing. In Proceedings of the 13th ACM conference on electronic commerce, EC ’12 (pp. 723–740). ACM, New York, NY, USA. https://doi.org/10.1145/2229012.2229068.
Manlove, D. F. (2013). Algorithmics of matching under preferences. Series on theoretical computer science (Vol. 2). Singapore: World Scientific.
Manlove, D. F., & O’Malley, G. (2008). Student-project allocation with preferences over projects. Journal of Discrete Algorithms, 6(4), 553–560. https://doi.org/10.1016/j.jda.2008.07.003.
Moulin, H. (2003). Fair division and collective welfare. Cambridge: The MIT Press.
Ogryczak, W., Pióro, M., & Tomaszewski, A. (2005). Telecommunications network design and max–min optimization problem. Journal of Telecommunications and Information Technology, 3, 43–56.
Perach, N., Polak, J., & Rothblum, U. G. (2008). A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. International Journal of Game Theory, 36(3), 519–535. https://doi.org/10.1007/s00182-007-0083-4.
Proll, L. G. (1972). A simple method of assigning projects to students. Operational Research Quarterly (1970–1977), 23(2), 195–201.
Rawls, J. (1971). A theory of justice. Cambridge, MA: Harvard University Press.
Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92(6), 991–1016.
Srinivasan, D., & Rachmawati, L. (2008). Efficient fuzzy evolutionary algorithm-based approach for solving the student project allocation problem. IEEE Transactions on Education, 51(4), 439–447. https://doi.org/10.1109/TE.2007.912537.
Tempkin, L. (1993). Inequality. New York: Oxford University Press.
Teo, C., & Ho, D. J. (1998). A systematic approach to the implementation of final year project in an electrical engineering undergraduate course. IEEE Transactions on Education, 41(1), 25–30. https://doi.org/10.1109/13.660783.
Williams, H. P. (2013). Model building in mathematical programming (5th ed.). Chichester: Wiley.
Yager, R. R. (1996). Constrained OWA aggregation. Fuzzy Sets and Systems, 81(1), 89–101. https://doi.org/10.1016/0165-0114(95)00242-1.
Yager, R. R. (1997). On the analytic representation of the leximin ordering and its application to flexible constraint propagation. European Journal of Operational Research, 102(1), 176–192. https://doi.org/10.1016/S0377-2217(96)00217-2.
Young, P. (1995). Equity: In theory and practice. Princeton, NJ: Princeton University Press.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chiarandini, M., Fagerberg, R. & Gualandi, S. Handling preferences in student-project allocation. Ann Oper Res 275, 39–78 (2019). https://doi.org/10.1007/s10479-017-2710-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-017-2710-1