KUniKIP - Optimization of Capacity Constrained Events



KUniKIP is an optimization tool for the construction of optimized event schedules for the yearly event KinderUni of the Freie Universität Berlin. For a few days the FU offers a selection of courses with differing dates school classes with children aged between 8 to 12 years can apply for. These classes are then to be assigned to single course dates according to their preferences. However, the courses usually come with capacity and other restrictions and can thus not cover the huge number of applications. We therefore desire an "optimal" solution under the given circumstances and custom parameters to give as many children as possible the chance to participate. KUniKIP allows us to do just that by modeling the multiple knapsack problem.
Herein the courses are interpreted as knapsacks and the classes as the items we want to distribute over the knapsacks. The classes' weight is given by the amount of pupils in them. The objective function is formulated in respect to what property we seek to maximize, be it the number of pupils, classes, (first-time-)schools or the number of dates with an assignment. KUniKIP will also, to some extend, analyze the given problem to give more insight in the quality of the solution.
KUniKIP is written in Perl and utilizes the ZIB Optimization Suite. It is available for Windows and Linux OS and should be adaptable to similar problems. The program and the math behind it are the result of a Diploma thesis that emerged from a joint project of the Zuse Institute Berlin (ZIB) and the Freie Universität Berlin (FU) and was improved and refined by several developers after. It is still being maintained at the ZIB and in use by the FU's KinderUni.

Authors and Developers
Biliana Boeva, Ralf Borndörfer, Gerwin Gamrath, Boris Grimm, Fabian Löbel, Nils Paetsch
Installation of Perl and...
...either a Linux OS with the ZIB Optimization Suite installed (SCIP and ZIMPL)
...or a Windows OS (the download contains SCIP and ZIMPL binaries for Windows)
Biliana Boeva - Veranstaltungsplanung mit Multiple-Knapsack-Methoden (Diploma thesis) (German)
Gerwin Gamrath - Praktikumsbericht 2013 (internship report) (German)
README: .pdf, .txt, .tex
Download KUniKIP 1.4 for Linux
Download KUniKIP 1.4 for Windows
developed at Zuse Institute Berlin
contact: Prof. Dr. Ralf Borndörfer
This site was last edited on the 8th August 2023 by Fabian Löbel
Disclaimer of warranty: No warranty whatsoever is given for the content of external links. The content of linked pages is solely the responsibility of the providers of those pages.
The usage of external pictures is explictely allowed by the holders of their rights.