Kindergarten allocation in Norway: An integer programming approach

Kindergartens are vital to society in many countries, and in Norway, the municipalities are the local authorities that facilitate a coordinated admission process involving all their kindergartens. Allocating children to kindergartens is a very time-consuming task that is usually done manually. Therefore, we propose two integer programming (IP) models to support this task. Both models include the children’s prioritized kindergarten, prioritization of children with special needs, siblings already placed in a kindergarten and traveling times, while the second (extended) model also ensures gender and age balance in the kindergartens. To solve the largest instances found in Norway, we propose a heuristic variable reduction scheme. The models are solved with a commercial solver and have been tested on real data from Tønsberg municipality, as well as on larger instances reflecting the municipalities of Trondheim and Oslo. The model solutions are compared to the solutions from the allocation scheme used in Tønsberg and it is shown that the optimization models provide significantly better solutions. The models are being implemented into an existing kindergarten administration software and will be tested by a few selected municipalities. If this is successful, it will be rolled out to more than 50 municipalities currently using this software.