KUniKIP ZUR AUSLASTUNGSOPTIMIERUNG VON VERANSTALTUNGEN ====================================================================================== ====================================================================================== 0. Inhalt 1. Allgemeine Informationen 2. Das Multiple Knapsack Problem 3. Uebertragung auf das Problem der KinderUni 4. Struktur und Systemvorraussetzungen 5. Daten und Datenformate 6. Verwendung und Optionen 7. Ausgabe ====================================================================================== 1. Allgemeine Informationen - Version: 1.1 - Datum: September 2012 - Autor: Biliana Boeva Nils Paetsch (Zuse-Institut Berlin, http://www.zib.de/) Gerwin Gamrath ====================================================================================== 2. Das Multiple Knapsack Problem Das Multiple Knapsack Problem (MKP) ist die Generalisierung des Single Knapsack Problems von einem Rucksack (Knapsack) auf mehrere Rucksaecke mit jeweils verschiedenen Kapazitaeten. Gegeben ist eine Menge von Gegenstaenden mit jeweiligem Profit und Gewicht und darueberhinaus eine Menge von Rucksaecken mit zulaessiger Kapazitaet. Das Ziel des MKP ist es eine Menge von Gegenstaenden zu finden und den einzelnen Rucksaecken zuzuordnen, so dass der Gesamtprofit aller zugeordneten Gegenstaende maximal ist, unter den Nebenbedingungen, dass die Summe der Kapazitaeten der Gegenstaende in den einzelnen Rucksaecken nicht die erlaubte Gesamtkapazitaet des jeweiligen Rucksacks uebersteigt. ====================================================================================== 3. Uebertragung auf das Problem der KinderUni Bei der KinderUni tritt folgende Problemstellung auf. Zu einer gegeben Anzahl an Kursen koennen sich Schulklassen anmelden, die dann unter Beruecksichtigung ihrer Praeferenzen den einzelnen Kursen zugeordnet werden sollen. Das Angebot der Kurse kann im Normalfall die grosse Nachfrage der Anmeldungen nicht decken. Das Problem der Auslastungsoptimierung der KinderUni wird durch eine Formulierung als mathematisches Optimierungsmodell als ein Multiple Knapsack Problem realisiert. Die einzelnen Kurse werden als Ruecksaecke interpretiert und die verschiedenen Schulklassen als die zuzuordnenden Gegenstaende. Die Zielfunktion, die sich aus den Bewertungen der Schulklassen ergibt, wird je nach entsprechender Gewichtung als eine Maximierung der Anzahl der Schueler, der Maximierung der neuen Schulen, der Maximierung der Anzahl der verschiedenen Schulen, der Maximierung der Anzahl der verschiedenen Klassen oder der maximalen Anzahl von belegten Terminen insgesamt formuliert, siehe 6. Seit Version 1.1 gilt es außerdem jene Schulen stark zu priorisieren, die sich in den vergangenen 2 Jahren angemeldet haben und nicht genommen wurden und sich nun zum dritten Mal in Folge wieder angemeldet haben. Dies soll sicherstellen, dass die Schulen nicht immer wieder abgelehnt werden und sich deshalb in Zukunft garnicht mehr versuchen anzumelden aus dem Gefühl heraus "dass es ja eh nichts bringt". Neben den Kurskapazitaeten sind folgende Nebenbedingungen ebenfalls dem Problem zugefuegt: - Beruecksichtigung der Teilnahme der Schulen in vorausgegangenen Jahren. - Klassen, die sich um mehr als eine Klassenstufen unterscheiden koennen nicht dem gleichen Termin zugeordnet werden. - Konflikte zwischen einzelnen Klassen, siehe 5. - Weitere feste Einschraenken/Vorgaben fuer bestimmte Klassen, Kurse oder Termine, siehe 5. Fuer eine wesentlich dataillierte Darstellung, der exakten mathematischen Formulierungen und mehr Informationen zum KinderUni-Problem an sich, siehe Boeva, Biliana (2008) "Veranstaltungsplanung mit Multiple-Knapsack-Methoden". Diplomarbeit, TU Berlin. ====================================================================================== 4. Struktur und Systemvorraussetzungen Die grundsaetzliche Optimierung von KUniKIP und die Struktur des Programmablaufs beruhen auf Boeva, Biliana (2008) "Veranstaltungsplanung mit Multiple-Knapsack-Methoden". Diplomarbeit, TU Berlin. KUniKIP gliedert sich in einzelne Teilprogramme, geschrieben in Perl. Durch einmaligen optionalen Aufruf eines vorliegenden Perl Programms kann ein automatischer Ablauf der einzelnen Perlprogramme sowie die Generierung einer gemeinsame Ausgabedatei erreicht werden. Eingabe- und Ausgabeformate der Daten liegen in Textdateien im ASCII-Format vor, siehe 6. und 7. Die unterliegende Optimerungssoftware basiert auf der ZIB Optimization Suite, siehe http://zibopt.zib.de/ "The ZIB Optimization Suite is a tool for generating and solving mixed integer programs. It consists of the following parts - ZIMPL (http://zimpl.zib.de/) a mixed integer programming modeling language. ZIMPL is a command line program written in plain C and released under GNU GPL. It has been tested to compile under Linux/Intel, Solaris, Tru64, HPUX, IRIX, AIX and MacOS-X. Probably it will compile and run wherever GMP is available. ZIMPL has even been successfully compiled for Windows using MinGW and the GCC as a cross compiler. - SoPlex (http://soplex.zib.de/) an implementation of the revised simplex algorithm. It features primal and dual solving routines for linear programs. SoPlex is completely implemented in C++. The code should be compliant with the current ANSI standard. RTTI and STL (other than iostream) are not used. With a decent modern C++ compiler you should have a chance. SoPlex was tested with compilers from GNU, Compaq, Intel, SUN, HP, SGI, IBM, and even MS. - SCIP (http://scip.zib.de/) one of the fastest non-commercial mixed integer programming solvers. It is also a framework for Constraint Integer Programming and branch-cut-and-price. SCIP is completely implemented in C. The code should compile with any ANSI compliant C compiler. SCIP was tested with compilers from GNU, Compaq, Intel, SUN. The user can easily generate linear programs and mixed integer programs with the modeling language ZIMPL. The resulting model can directly be loaded into SCIP and solved. In the solution process SCIP may use SoPlex as underlying LP solver. Since all three tools are available in source code and free for academic use, they are an ideal tool for academic research purposes and for teaching integer programming." Entsprechend der Optimization Suite werden per Perlskript die mathematischen Modelle zur Verwendung mit ZIMPL generiert und diese dann von SCIP mit Hilfe von SoPlex geloest. ====================================================================================== 5. Daten und Datenformate Die Eingabedaten werden im ASCII-Format erwartet. Die Daten werden alle in der Datei daten/input.txt abgespeichert, so wie sie derzeit vom Server kommen, das heisst als fortlaufende Listen bezueglich der Anmeldungen einer Klassen-Id zu einer Termin-Id ("a" als Zeilenpraefix), der angemeldeten Klassen ("k"), der angemeldeten Schulen ("s"), der vorhandenen Termine ("t") sowie einer Liste aller moeglichen Schulen ("v") zum Vergleich mit den Anmeldungen aus vergangenen Jahren. Der Zeilenpraefix "c" steht fuer Kommentarzeilen. Siehe folgenden Auszug Auszug der Datei 'daten/input.txt' als Beispiel: c anm_id klassen_id termin_id. kl_gr. a 2286 310 495 14 c klassen_id schul_nr klassenname klassenstufe bezirk k 310 235 5e 5 Steglitz-Zehlendorf c schul_nr bezirk name s 12 Mitte Moabiter_Grundschule c termin_id kurs_nr kapazitaet kuni_times_id t 490 77 41 490 c school_id_2009 name teilgenommen_2007 teilgenommen_2008 v 375 29._Schule_(Grundschule) 0 0 Die Datei 'daten/bezirke.txt' enthaelt eine Liste aller moeglichen Berliner Bezirke, die zur Ueberpreufung ob die Anmeldungen aus Berlin selbst oder dem Berliner Umland kommen, genutzt wird. Konflikte zwischen einzelnen Schulklassen werden mit Eintraegen in der Datei 'daten/konflikte.txt' behandelt, das heisst die zu einer Termin-Id eingetragenen zwei Klassen-Ids (mit Zeilen-Praefix "p") werden nicht gemeinsam zu dem bestimmten Termin zugeordnet, siehe als Beispiel c Konfliktbedingungen fuer bestimmte Kurse/Klassen c ------------------------------------------------ c termin_id klassen_id klassen_id p 490 435 436 Termine fuer die nur eine einzelne Klasse zugeordnet werden darf, werden (mit Zeilenpraefix "t") in der Datei 'daten/restriktionen.txt' hinterlegt, siehe als Beispiel c Feste Vorgabe: Nur eine Klasse pro Termin c ------------------------------------------------ c termin_id kurs_nr kapazitaet kuni_times_id t 669 80 24 669 In der Datei 'daten/vorgaben.txt' werden (mit Zeilen-Praefix "v") die Klassen-Ids abgespeichert, die auf jeden Fall irgendeinem Termin zugeordnet werden sollen, siehe als Beispiel c Feste Vorgaben fuer bestimmte Kurse/Klassen c ------------------------------------------------ c klassen_id v 488 Feste Zuweisungen von bestimmten Klassen-Ids zu bestimmten Termin-Ids werden (mit Zeilen-Praefix "z") in der Datei 'daten/zuweisungen.txt' hinterlegt, siehe als Beispiel c Feste Vorgaben fuer bestimmte Kurse/Klassen c ------------------------------------------------ c termin_id klassen_id z 672 451 Kapazitaetserhoehungen werden in der Datei 'daten/kapErhoehung.txt' festgehalten. Falls man sich also dazu entschieden hat eine Kapazitaetserhoehung fuer einen Kurs vorzunehmen, dann kann man dies hier festhalten und das Programm liest das auch bei der Erstellung des IPs ein. Hier ein Beipsiel c Kapazitaetserhoehungen c termin_id erhoehung t 1404 1 t 1294 2 ====================================================================================== 6. Verwendung und Optionen KUniKIP gliedert sich in vier Teilprogramme, geschrieben in Perl. - skripte/kip_main.pl [-x arg] [-y arg] [-z arg] [-m arg] [-n arg] das Hauptoptimierungsprogramm; dient zur Optimierung bezueglich der einzelnen Ziele - Maximierung der Schuelerzahl - Maximierung der Anzahl neuer Schulen - Maximierung der Anzahl Schulen - Maximierung der Anzahl Klassen - Maximierung der Anzahl Termine Das Skript erwartet folgende Uebergabeparater mit Wertangabe - -x: Gewichtungsfaktor fuer erste Zielfunktion - -y: Gewichtungsfaktor fuer zweite Zielfunktion - -z: Gewichtungsfaktor fuer dritte Zielfunktion - -k: Gewichtungsfaktor fuer vierte Zielfunktion - -t: Gewichtungsfaktor fuer fuenfte Zielfunktion - -m: Mindestanzahl an neuen Schulen fuer die eine Optimierung durchgefuehrt werden soll (Ist der Wert nicht angegeben, wird die Optimerung unanabhaengig von einer Mindestanzahl durchgefuehert) - -n: Mindestanzahl an Schulen insgesamt fuer die eine Optimierung durchgefuehrt werden soll (Ist der Wert nicht angegeben, wird die Optimerung unanabhaengig von einer Mindestanzahl durchgefuehert) - skripte/kip_gapAnalization.pl [-x arg] [-y arg] [-z arg] [-k arg] [-t arg] zur Berechnung der theoretisch maximalen Auslastung der Veranstaltung. Berechnet die sogenannte "Single-Knapsack-Gap" fuer jeden einzelnen Termin und summiert diese anschliessend auf Das Skript erwartet folgende Uebergabeparater mit Wertangabe - -x: Gewichtungsfaktor fuer erste Zielfunktion - -y: Gewichtungsfaktor fuer zweite Zielfunktion - -z: Gewichtungsfaktor fuer dritte Zielfunktion - -k: Gewichtungsfaktor fuer vierte Zielfunktion - -t: Gewichtungsfaktor fuer fuenfte Zielfunktion - skripte/kip_eConstraint.pl [-x arg] [-y arg] [-z arg] [-k arg] [-t arg] [-l arg] [-u arg] zur Berechnung des bikriteriellen Optimierungsproblem "Maximale Schueleranzahl versus maximale Anzahl neuer Schulen" mit Hilfe einer sogenannten Epsilon-Constraint- Skalarisierung Das Skript erwartet folgende Uebergabeparater mit Wertangabe - -x: Gewichtungsfaktor fuer erste Zielfunktion - -y: Gewichtungsfaktor fuer zweite Zielfunktion - -z: Gewichtungsfaktor fuer dritte Zielfunktion - -k: Gewichtungsfaktor fuer vierte Zielfunktion - -t: Gewichtungsfaktor fuer fuenfte Zielfunktio - -l: minimale Anzahl an neuen Schulen fuer die die Optimerung durchgefuehrt werden soll - -u: maximale Anzahl an neuen Schulen fuer die die Optimerung durchgefuehrt werden soll - skripte/kip_capacityIncrement.pl [-x arg] [-y arg] [-z arg] [-k arg] [-t arg] [-m arg] [-c arg] zur Betrachtung der Moeglichkeit von Kapazitaetserhoehungen der einzelnen Termine und der damit verbunden Auswirkung auf die Erhoehung der Gesamtanzahl der zugewiesenen Schuelerzahl Das Skript erwartet folgende Uebergabeparater mit Wertangabe - -x: Gewichtungsfaktor fuer erste Zielfunktion - -y: Gewichtungsfaktor fuer zweite Zielfunktion - -z: Gewichtungsfaktor fuer dritte Zielfunktion - -k: Gewichtungsfaktor fuer vierte Zielfunktion - -t: Gewichtungsfaktor fuer fuenfte Zielfunktio - -m: Wert der Kapazitaetserhoehung bis zu der in 1-Schrittweite eine Optimerung durchgefuehrt werden soll. - -c: Mindestanzahl an neuen Schulen fuer die eine Optimierung durchgefuehrt werden soll (Ist der Wert nicht angegeben, wird die Optimerung unanabhaengig von einer Mindestanzahl durchgefuehert) Folgendes Beispiel zum Aufruf des Hauptskriptes soll die Nutzung demonstrieren: skripte/kip_main.pl -x 1 -y 0.00001 -z 0.000001 -k 0.000001 -t 0.00001 -m 40 Die oben erwaehnten Skripte beinhalten im wesentlichen nur das Einlesen der Daten und der Erstellung der Ausgaben durch Parsen der Textausgaben der unterliegenden Optimerungssoftware. Aufgrund von internen Abhaengigkeiten muss der Aufruf der einzelnen Skripte aus dem Hauptordner kommen. Die Erstellung der jeweiligen mathematischen Modelle, basierend auf den Eingabedaten, geschieht dann teilprogramm-abhaengig in - skripte/zimplmodel.pl Hier ist das grundlegende Hauptmodell zum KinderUni-Problem abgelegt, welches je nach aufrufendem Programm entsprechend angepasst wird. Veraenderungen oder Erweiterungen am Gesamtmodell oder an den einzelnen Modellen werder hier vorgenommen. Das im Hauptordner vorliegende Perlprogramm - kunikip.pl [-k arg] kann optional dazu genutzt werden, durch einmaligen Aufruf, die einzelnen Teilprogramme nacheinander automatisch ablaufen zu lassen. Das Skript erwartet zwei Zahlen als Uebergabeparameter. Die obligatorische Integerzahl (-k) gibt die Anzahl der Kapazitaetserhoehungen fuer die eine Berechnung durchgefuehrtwerden soll an. Bis auf Warnungs- und Fehlerausgaben werden die Konsolenausgabe der Berechnungsprogramme in die Date 'ergebnisse/ausgabe.txt' umgeleitet. Die Parameter fuer die einzelnen Perlskripte werden in diesem Fall automatisch berechnet. Folgendes Beispiel zum Aufruf des Perlprogramm soll dessen Nutzung demonstrieren: perl kunikip.pl -k 3 ====================================================================================== 7. Ausgabe Bei Verwendung des globalen Perlprogramms 'kunikip.pl' wird eine einzelne Ausgabedatei 'analyse.txt' im Hauptordner erstellt in der alle benoetigten Informationen der einzelnen Programmschritte aufgelistet sind. - 1. Datenanalyse - Auflistung der Klassen mit unterschiedlichen Anmeldegroessen zu unterschiedlichen Terminen. - Auflistung der Anmeldungen von Klassen mit mehr als 30 Schuelern. - 2. Optimierung bezueglich maximaler Anzahl von Schuelern - 3. Optimierung bezueglich maximaler Anzahl von Schulen - 4. Optimierung bezueglich maximaler Anzahl von neuen Schulen - 5. Optimierung bezueglich maximaler Anzahl von Klassen - 6. Optimierung bezueglich maximaler Anzahl von belegten Terminen - 7. Sensitivitaetsanalyse Anzahl Schueler vs. Anzahl neuer Schulen - 8. Sensitivitaetsanalyse Anzahl Schueler vs. Anzahl Schulen: - 9. Sensitivitaetsanalyse zur Terminkapazitaet Im Ordner 'ergebnisse' werden analog zum Namen der einzelnen Perlskripte die entsprechenden Ausgaben hinterlegt. Darunter sind auch die von den Skripten temporaer erstellten mathematischen Modelle. Folgende Dateien beinhalten relevanten Inhalt: - ergebnisse/kip_main-detail.txt Ergebnis der Loesung im Detail. - ergebnisse/kip_main-db.txt Ergebnis der Berechnungen zum Upload in die Datenbank. Datei besteht aus Zeilen mit jeweils drei Werten (Anmeldungs-Id, Termin-Id, Klassen-Id) Beachte: Es wird jene Loesung in kip_main-db.txt geschrieben, mit der am Ende von kunikp.pl die Sensitivitaetsanalyse zur Terminkapazitaet ('skripte/kip_capacityIncrement.pl') durchgefuehrt wird. Bei Bedarf also dort aendern! - ergebnisse/kip_gapAnalyzation.txt Auflistung der nicht zuordbaren Terminkapazitaet pro Termin und der entsprechenden Gesamtsumme. - ergebnisse/kip_eConstraint.txt Ergebnis der bikriteriellen Optimierung "Maximierung Anzahl Schueler versus Maximierung Anzahl neuer Schulen". Die Zeilen der Datei bestehen aus den Werten Anzahl neue Schulen, Anzahl Schulen (gesamt), zugeordnete Klassen, Schueler, belegte Termine. - ergebnisse/kip_eConstraint2.txt Ergebnis der bikriteriellen Optimierung "Maximierung Anzahl Schueler versus Maximierung Anzahl Schulen". Die Zeilen der Datei bestehen aus den Werten Anzahl neue Schulen, Anzahl Schulen (gesamt), zugeordnete Klassen, Schueler, belegte Termine. - ergebnisse/kip_capacityIncrement.txt Angabe welche Kurse durch Kapazitaetserhoehungen eine Gesamterhoehung der Schuelerzahl ermoeglichen. Bei Verwendung des Perlprogramms 'kunikip.pl' werden diese in die Datei 'ergebnisse/ausgabe.txt' umgeleitet. ======================================================================================