Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 17

Communication Papers of the 2018 Federated Conference on Computer Science and Information Systems

"Passeport Vacances": an assignment problem with cost balancing


DOI: http://dx.doi.org/10.15439/2018F230

Citation: Communication Papers of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 17, pages 5359 ()

Full text

Abstract. Passeport Vacances is an offer for school-aged children to discover a set of activities during holidays. For more than 30 years, it has been an established social function in several countries, including Germany and Switzerland. Proposed activities might occur several times during the Passeport Vacances. The assignment of activities to children is computed in order to maximize the children's preferences, as well as to balance each child's incurred cost, toward an equity goal. There are several sets of constraints associated with the assignment problem: no overlapping activities assigned to the same child, minimal and maximal ages per activity, minimum number of children for opening an activity, maximal size of a group for each activity, no similar activities assigned to the same child, no already assigned `lifetime'-activity per child, and at most one activity per period and per child. We propose a binary linear programming model that describes the assignment problem, report CPU computation issues regarding the model implementation, and report numerical results based on a state-of-the-art MIP solver. Tests where conducted with real data from the 2016 edition of Passeport Vacances in Morges.


  1. F. Uney-Yuksektepe and İ. Karabulut, “Mathematical programming approach to course-teaching assistant assignment problem,” in Proceedings of the 41st International Conference on Computers & Industrial Engineering, 2011, pp. 878–883.
  2. Y. Z. Ünal and Ö. Uysal, “A new mixed integer programming model for curriculum balancing: Application to a turkish university,” European Journal of Operational Research, vol. 238, no. 1, pp. 339–347, 2014. http://dx.doi.org/https://doi.org/10.1016/j.ejor.2014.03.015
  3. R. de la Torre, A. Lusa, and M. Mateo, “A MILP model for the long term academic staff size and composition planning in public universities,” Omega, vol. 63, pp. 1–11, sep 2016. http://dx.doi.org/10.1016/j.omega.2015.09.008
  4. E. L. Bouzarth, R. Forrester, K. R. Hutson, and L. Reddoch, “Assigning students to schools to minimize both transportation costs and socioeconomic variation between schools,” Socio-Economic Planning Sciences, sep 2017. http://dx.doi.org/10.1016/j.seps.2017.09.001
  5. B. Domenech and A. Lusa, “A MILP model for the teacher assignment problem considering teachers’ preferences,” European Journal of Operational Research, vol. 249, no. 3, pp. 1153–1160, mar 2016. http://dx.doi.org/10.1016/j.ejor.2015.08.057
  6. L. Pan, S. Chu, G. Han, and J. Z. Huang, “Multi-criteria student project allocation: A case study of goal programming formulation with dss implementation,” in The Eighth International Symposium on Operations Research and Its Applications (ISORA’09), Zhangjiajie, China, 2009, pp. 75–82.
  7. I. Kim and O. de Weck, “Adaptive weighted-sum method for biobjective optimization: Pareto front generation,” Structural and Multidisciplinary Optimization, vol. 29, no. 2, pp. 149–158, sep 2004. http://dx.doi.org/10.1007/s00158-004-0465-1
  8. J. Bezanson, S. Karpinski, V. B. Shah, and A. Edelman, “Julia: A fast dynamic language for technical computing,” CoRR, vol. abs/1209.5145, 2012. [Online]. Available: http://arxiv.org/abs/1209.5145
  9. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM Review, vol. 59, no. 1, pp. 65–98, 2017. http://dx.doi.org/10.1137/141000671. [Online]. Available: http://julialang.org/publications/julia-fresh-approach-BEKS.pdf
  10. [Online]. Available: http://www.gurobi.com/
  11. [Online]. Available: https://julialang.org