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.0 - Datum: November 2009 - Autor: Biliana Boeva Nils Paetsch (Zuse-Institut Berlin, http://www.zib.de/) ====================================================================================== 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 oder der maximalen Anzahl von verschiedenen Schulen insgesamt formuliert, siehe 6. Neben den Kurskapazitaeten sind folgende Nebenbedingungen ebenfalls dem Problem zugefuegt: - Beruecksichtigung der Teilnahme der Schulen in vorausgegangenen Jahren. - Klassen, die sich um mehr als zwei 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 Shell-Skriptes (bash) 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 ====================================================================================== 6. Verwendung und Optionen KUniKIP gliedert sich in vier Teilprogramme, geschrieben in Perl. - skripte/kip_main.pl [-x arg] [-y arg] [-z arg] [arg -m] das Hauptoptimierungsprogramm; dient zur Optimierung bezueglich der einzelnen Ziele - Maximierung der Schuelerzahl - Maximierung der Anzahl neuer Schulen - Maximierung der Anzahl Schulen Das Skript erwartet folgende Uebergabeparater mit Wertangabe - -x: Gewichtungsfaktor fuer erste Zielfunktion - -y: Gewichtungsfaktor fuer zweite Zielfunktion - -z: Gewichtungsfaktor fuer dritte 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) - skripte/kip_gapAnalization.pl [-x arg] [-y arg] [-z 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 - skripte/kip_eConstraint.pl [-x arg] [-y arg] [-z 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 - -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] [-m arg] [-k 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 - -m: Wert der Kapazitaetserhoehung bis zu der in 1-Schrittweite eine Optimerung durchgefuehrt werden soll. - -k: 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.0001 -z 0.0001 -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 Shell-Skript (bash) - kunikip.sh [-k arg] [-p arg] [-h] kann optional dazu genutzt werden, durch einmaligen Aufruf, die einzelnen Teilprogramme nacheinander automatisch ablaufen zu lassen. Das Skript erwartet zwei Zahlen als Uebergabeparameter. Als erstes (-k) eine obligatorische Integerzahl die die Anzahl der Kapazitaetserhoehungen fuer die eine Berechnung durchgefuehrtwerden soll. Der zweite Parameter (-p) ist eine 0/1-boolean- Variable. Der Wert '1' gibt an, dass bis auf Warnungs- und Fehlerausgaben die Konsolenausgabe der Berechnungsprogramme in die Date 'ergebnisse/ausgabe.txt' umgeleitet wird. Die Parameter fuer die einzelnen Perlskripte werden in diesem Fall automatisch berechnet. Bei Benutzung des Parameters -h fuer die Hilfe (bzw. die Verwendung des Skripts geoeffnet). Folgendes Beispiel zum Aufruf des Shellskriptes soll dessen Nutzung demonstrieren: kip.sh -k 3 -p 1 ====================================================================================== 7. Ausgabe Bei Verwendung des globalen Shell-Skriptes 'kunikip.sh' wird eine einzelne Ausgabedatei 'ausgabe.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. Sensitivitaetsanalyse Anzahl Schueler vs. Anzahl neuer Schulen - 6. 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) - 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_capacityIncrement.txt Angabe welche Kurse durch Kapazitaetserhoehungen eine Gesamterhoehung der Schuelerzahl ermoeglichen. Bei Verwendung des Shell-Skriptes 'kunikip.sh' und der Unterdrueckung der der Konsolenausgaben der einzelnen Skripte und Unterprogramme, werden diese in die Datei 'ergebnisse/ausgabe.txt' umgeleitet. ======================================================================================