Abschlussarbeiten
Offene Themen
- Minimale Anzahl von Hinweisen bei Sudoku (Details), Ansprechpartner: Sascha Kurz
- K-Server Problem und der Arbeitsfunktionenalgorithmus (Details), Ansprechpartner: Sascha Kurz
- Selbstorganisierende Datenstrukturen (Details), Ansprechpartner: Sascha Kurz
- Eine effiziente Implementierung der Score-Fix-Adjust-Heuristik (Details), Ansprechpartner: Sascha Kurz
- Preisoptimierung und Nachfrageschätzung bei zensierten Daten (Details), Ansprechpartner: Sascha Kurz
- Die Score-Fix-Adjust-Heuristik (Details), Ansprechpartner: Sascha Kurz
- Minimal orientierter Durchmesser (Details), Ansprechpartner: Sascha Kurz
- Optimierte Strategien für Sportspiele auf Basis Markovscher Entscheidungsprobleme,
In Zusammenarbeit mit dem Institut für Sportwissenschaft (IfS) der Universität Bayreuth soll die Evaluierung und Optimierung von Strategien in Sportspielen auf Basis Markovscher Entscheidungsprobleme untersucht werden. (Details), Ansprechpartner: Jörg Rambau
- Weitere Themen auf Anfrage.
Eigene Themenvorschläge sind ebenfalls möglich, sofern sie sich in das Profil des Lehrstuhls einfügen.
Laufende Bachelor-, Master-, Diplom- und Zulassungsarbeiten
- Christian Walter (Diplomarbeit): Überblick über Methoden zur Lösung des Universitätskursstundenplanungsproblems Im Universitätskursplanungsproblem geht es darum, Veranstaltungen Startzeiten und Räume so zuzuweisen, dass niemals zwei Veranstaltungen zur gleichen Zeit den selben Raum belegen und außerdem bestimmte Veranstaltungen nicht zeitgleich stattfinden. Praktische Probleminstanzen hiervon lassen sich jedoch nicht durch direktes Anwenden von Standardlösern bewältigen. In der Literatur findet sich deshalb eine Vielzahl von Techniken, die im Stande sind dieses Problem auch für realistische Daten zu lösen. In dieser Diplomarbeit soll ein Überblick über exakte mathematische Verfahren zur Lösung des Universitätskursstundenplanungsproblems erstellt werden.
Abgabe: 31.03.2013
Abgeschlossene Bachelor-, Master-, Diplom- und Zulassungsarbeiten
- Stefan Müller (Bachelorarbeit): Gewichtete Mediane -- Wieviel Einfluss hat der einzelne Bürger? In der Praxis werden recht häufig zweistufige Abstimmungsverfahren benutzt, d.h. die breite Bevölkerungsmasse bestimmt in einer ersten Stufe zunächst Repräsentaten. Dies geschieht in der Regel in grösseren Zeitabständen. Das regelmässige Tagesgeschäft wird dann von den Repräsentanten in der zweiten Stufe entschieden. Den Einfluß den der einzelne Bürger auf die Wahl seines Repräsentanten hat, wird gewöhnlich mit Hilfe der Wahrscheinlichkeit, der Medianwähler zu sein, gemessen. In der zweiten Stufe werden oft Gewichte für die einzelnen Repräsentanten verwendet, so dass der Einfluss eines Repräsentanten als Wahrscheinlichkeit der gewichtete Median der zweiten Stufe zu sein, gemessen werden kann. Das Verständnis von Zusammenhängen, die diese Einflüsse, sowohl die direkten innerhalb einer Stufe, als auch die indirekten über beide Stufen hinweg, beeinflussen, ist z.B. wichtig für das Design von fairen Abstimmungsverfahren.
Abgabe: 31.07.2012 - Jonas Hoffmeister (Bachelorarbeit): Das inverse Machtindexproblem für den Nucleolus Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als "fair" an. Aber dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Für verwickeltere Situationen gibt es mehrere sogenannte Machtindizes, mit denen man eine reelle Zahl als Maß für die Macht eines Landes ausrechnen kann. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Im Rahmen dieser Bachelorarbeit soll der Stand der Dinge des inversen Machtindexproblems für den Penrose-Banzhafindex (PBI) beschrieben und für den Nucleolus als weiteres, robusteres, Machtmass übertragen werden.
Abgabe: 16.07.2012 - Maria Juraschik (Bachelorarbeit): Dispositionsoptimierung bei einem Internetbuchhändler Ein Online-Händler verkauft einen großen Artikelkatalog in mehreren Online Shops. Das Lagern der Artikel und Versenden der Bestellungen wird von verschiedenen Fullfillment Dienstleistern durchgeführt. Bei der Zuordnung von Bestllungen zu den einzelnen Dienstleistern sind einige Restriktionen zu beachten. Nicht jeder Artikel wird von jedem Dienstleister angeboten bzw. ist nicht aktuell verfügbar; wobei die Verfügbarkeitsinformationen von unterschiedlicher Güte sind. Für bestimmte Artikel gibt es Rabattverträge, die an monatliche Mindestabnahmemengen gekoppelt sind. Wie kann man unter diesen Nebenbedingungen bzw. Unsicherheiten eine erlösmaximale Aufteilung von Bestellungen auf die verschiedenen Dienstleister bestimmen?
Abgabe: 30.06.2012 - Marcus Hassa (Diplomarbeit): Symmetrische ganzzahlige lineare Programme mit Anwendungen in der Kodierungstheorie Bei vielen kombinatorischen motivierten Modellierungen in der Sprache der ganzzahlig-linearen Programmierung gibt es vielfältige Symmetrien in der Formulierung. Das heißt, dass es zu jeder zulässigen Lösung eine ganze Menge an äquivalenten zulässigen Lösungen mit demselben Zielfunktionswert gibt. Diese Eigenschaft ist für die Standard-ILP-Löser wie beispielsweise CPLEX oder Gurobi sehr schlecht, weil sie immer wieder dieselben Schranken berechnen.
Der optimale Ausweg wäre sich die Symmetrie beim Branch-and-Bound-Baum zu Nutze zu machen. Zu eben diesem Thema gibt es ein paar Arbeiten, die im Rahmen dieser Diplomarbeit anhand zweier spezifischer Anwendungsprobleme aus der Kodierungstheorie beschrieben und implementiert werden sollen. Abgabe: 30.06.2012 - Svitlana Mirochnik (Diplomarbeit): Logistische Regression zur Schätzung von Verkäufen bei einem TextildiscounterAn der Universität Bayreuth läuft seit 2007 ein von der Bayerischen Forschungsstiftung gefördertes Praxisprojekt zur Entwicklung eines Integrierten Systems zur Größen- und Preisoptimierung bei einem Textildiscounter (DISPO). Grundlage ist ein stochastisches gemischt-ganzzahliges Programm für die Warenverteilung, in dem Preisreduzierungen als Kompensationsentscheidung für Fehlbelieferungen dienen. Entscheidungen erfolgen auf Grundlage geschätzter Verkäufe pro Filiale und Größe abhäangig von Verkaufswoche, Preis und Szenario. Wegen geringer Verkaufszahlen pro Filiale schlagen klassische lineare Regressionsverfahren fehl. Momentan ist daher eine im Rahmen des Projekts entwickelte empirische Nachfrageschätzung im Einsatz. Verglichen soll diese nun mit einer nichtlinearen klassischen Methode zur Nachfrageschätzung bei binären bzw. ordinalen abhängigen Variablen, der logistischen Regression. Aufgabe der Diplomarbeit ist nun die Entwicklung, die Analyse, die Implementierung und die experimentelle Untersuchung einer Schätzung der Verkäufe durch logistische Regression anhand realer Daten. Abgabe: 30.11.2011
- Pavlo Dyban (Masterarbeit): Die Integer-L-Shaped-Methode. Die L-Shaped-Methode ist eine spezielle Form der iterativen Lösung der Benders-Zerlegung eines stochastischen linearen Programms in extensiver Form. Dieses Verfahren überträgt sich nicht unmittelbar auf den Fall ganzzahliger linearer Programme. In modifizierter Form erhält man allerdings eine Methode für den Fall vollständiger Kompensation. Thema dieser Masterarbeit ist Entwurf und Implementierung einer solchen L-Shaped-Methode für stochastische ganzzahlige lineare Programme mit vollständiger Kompensation sowie Testrechnungen auf verschiedenen Beispielanwendungen. Abgabe: 30.09.2011
- Madeline Lips (Diplomarbeit): Windenergieprognosen -- Potenzial stochastischer Optimierung. An der European Energy Exchange (EEX) Energiebörse mit Sitz in Leipzig werden tagtäglich Preise für Energie ausgehandelt. Durch das Erneuerbare-Energien-Gesetz besitzen Windkraft und andere erneuerbare Energien gegenüber fossilen Brennstoffen und Kernkraft eine Vorrangstellung. In Folge dessen hängt der Strompreis an der EEX sehr stark von der aktuellen Leistung von Kraftwerken erneuerbarer Energien wie Windkraftwerken ab. Eine möglichst genaue Prognose der zukünftig produzierten Leistung ist somit u.a. für Stromnetzbetreiber essentiell. Hat man mehrere Prognosen zur Verfügung, so stellt sich die Frage, wie man aufgrund dessen optimal (z.B. über Ankaufs- und Verkaufsmengen) entscheiden soll. Eine Möglichkeit ist es, die Prognosen zu einer einzigen (z.B. als gewichtete Summe) Prognose zusammenzufassen und anschließend optimal zu entscheiden. Anhand historischer Daten kann man versuchen die vorhandenen Freiheitsgrade möglichst effektiv zu nutzen. Ein anderer Ansatz mit dieser mehrdeutigen Information umzugehen, ist die unsichere Information in die Optimierung mit einzubeziehen anstatt sie vorab zu eliminieren -- sogennante stochastische Optimierung. Abgabe: 12.12.2011
- Bianca Lindner (Diplomarbeit): Optimalsteuerung von Meinungsbildungsdynamiken. Viele Prozesse unserer Welt unterliegen einer Meinungsdynamik. Dies bedeutet, dass jedes einzelne Individuum eine Meinung zu einem gegebenen Thema hat, sich diese aber durch Kommunikation mit anderen Individuen im Laufe der Zeit ändert. Ein theoretisches Modell Meinungsbildungsdynamiken zu beschreiben ist das sogennannte Bounded Confidence-Modell. Hierbei wird die eigene Meinung nur von anderen Meinungen beeinflusst, die nicht zu stark hiervon abweichen. Anhand dieses Modells lassen sich schon ein paar Phänomene von Meinungsbildungsdynamiken analysieren. Richtig spannend wird es allerdings, wenn man versucht die Meinungsbildungsdynamik zu beeinflussen. Abgabe: 07.10.2011
- Maria Gundermann (Diplomarbeit): Das Inverse Machtindexproblem. Tritt neues Land der Europäischen Union oder einem anderen Verbund bei, so kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Allgemein anerkannt ist, dass bevölkerungsreiche Länder mehr Macht haben sollen als bevölkerungsarme Länder. Auch über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als fair an.
Um Machtanteile zu messen gibt es mehrere sogenannte Machtindizes. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Es gilt, die Abweichung zwischen dem sich aus der Bevölkerungsanzahl ergebenden, gerechten Machtanteil und der sich aus den Stimmgewichten ergebenden, tatsächlichen Macht zu minimieren.
Im Rahmen dieser Diplomarbeit sollen fortgeschrittene Methoden der Ganzzahligen Linearen Optimierung auf eine ILP-Formulierung des Problems angewendet werden, mit dem Ziel beispielhaft eine faire (inkl. Gütegarantien) Stimmgewichtsverteilung der EU27 zu berechnen bzw. die aktuellen Rechengrenzen weiter zu verschieben. Abgabe: 31.07.2011 - Andreea Giurgiu (Diplomarbeit): Effizientes Lernen monotoner boolscher Funktionen. In komplexen Systemen (mit Ressourcenbeschränkungen) und vielen Einzelkomponenten kann es zu Fehlern kommen, wenn bestimmte Kombinationen von Einzelkomponenten gleichzeit aktiv sind. Als anschauliches Beispiel kann man sich einen Computer vorstellen, auf dem unterschiedliche Programme ausgeführt werden können, beispielsweise ein Textverarbeitsprogramm, ein Internetbrowser, ein Tabellenkalkulationsprogramm und ein Graphikprogramm. Nehmen wir einmal an, dass der Computer abstürzt, wenn alle vier Programme gleichzeitig ausgeführt werden, so sind wir daran interessiert herauszufinden, bei welchen Kombinationen der Computer abstürzt und bei welchen er stabil weiter läuft.
Bei N verschiedenen Programmen gibt es theoretisch 2N Kombinationen, in denen der Computer entweder abstürzen oder stabil weiter laufen kann. Es ist aber nicht unrealistisch eine gewisse Monotonie anzunehmen: Läuft der Computer bei gleichzeitiger Ausführung der Textverarbeitung und der Tabellenkalkulation weiter, so ist davon auszugehen, dass er auch bei alleiniger Ausführung eines der beiden Programme stabil weiter läuft. Führen dagegen bereits die Programme Textverarbeitung, Tabellenkalkulation und der Internetbrowser zu einem Absturz, so wird das System auch bei gleichzeitiger Verwendung aller vier Programm abstürzen. Mathematisch lässt sich das Fehlerverhalten eines solchen Systems als monotone boolsche Funktion beschreiben.
Ziel ist es, die monotone boolsche Funktion eines Systems durch Auswertungen an Stützpunkten vollständig zu bestimmen. Hier kann man sich vorstellen, dass man beispielsweise ein Experiment durchführt (die Programme in der gewählten Kombination auf dem Rechner laufen lassen und beobachten, was passiert) oder Experten befragt. Da eine solche Auswertung in der Regel teuer ist, soll die Anzahl der notwendigen Auswertungen minimiert werden. Abgabe: 30.06.2011 - Katharina Drobinin (Diplomarbeit): Methoden der Benders-Zerlegung für das Universitätskursplanungsproblem. An der Universität Bayreuth läuft seit 2010 ein von der Oberfrankenstiftung gefördertes Projekt zur automatischen Unterstützung der Zeit- und Raumplanung für Lehrveranstaltungen. Die Planungsaufgabe ist in der mathematischen Literatur bekannt als das Universitätskursplanungsproblem. Ein Modellierungsansatz von Lach und Lübbecke hat sich als ein Spezialfall der Generierung von Benders-Schnitten herausgestellt. Daher wird diese Technik nun genauer untersucht. Aufgabe der Diplomarbeit ist der Entwurf, die Analyse, die Implementierung und die experimentelle Untersuchung verschiedener Verfahren zur Auswahl von Benders-Schnitten für das Universiätskursplanungsproblem. Abgabe: 31.03.2011
- Peter Hoffmann (Diplomarbeit): Scanstrategien beim Strahlschmelzen. Um kundenindividuelle Produkte mit hoher Komplexität in immer kürzer werdenden Entwicklungs- und Produktionszyklen aus unterschiedlichen metallischen Werkstoffen zu fertigen, werden sogenannte Strahlschmelzverfahren eingesetzt. Das Grundprinzip verschiedener Technologien ist dabei das selektive Verfestigen einkomponentiger Pulverwerkstoffe mittels einer Laserstrahlquelle. Durch Aufbringen mehrer Pulverschichten können dreidimensionale Objekte aus unterschiedlichen metallischen Werkstoffen gefertigt werden. Die durch den Laser lokal eingebrachte hohe Energie kann zu Verzügen und Eigenspannungen führen (Stichwort Temperature-Gradient-Mechanism – TGM). Die Reihenfolge (auch Scanstrategie genannt), in der die Pulverwerkstoffe verfestigt werden, spielt somit eine große Rolle. Eine Möglichkeit, Verzügunge und Eigenspannungen zu vermeiden, könnte sein, Scanstrategien zu verwenden, welche einen möglichst großen Abstand zwischen zwei zeitlich aufeinander folgenden Verfestigungen besitzen. Mathematisch führt diese Überlegung beispielsweise zum Maximum Scatter TSP Problem. Im Rahmen der Diplomarbeit soll das Anwendungsproblem und die zugrunde liegende Physik beschrieben werden (Stichwort: instationäre Wärmeleitungsgleichung). Durch Vereinfachen der Problemstellung (Diskretisierung, Linearisierung, zweidimensionale Sichtweise, ...) sollen diskrete Optimierungsprobleme extrahiert werden, die beispielsweise mit Methoden der ganzzahligen linearen Optimierung gelöst werden können. Die Betrachtung stark vereinfachter aber charakteristischer Teilprobleme kann zum Entwickeln geeigneter Heuristiken verwendet werden. Abgabe: 31.10.2010
- Nadja Popp (Diplomarbeit): Mechanismus-Design. Aufgabe ist eine Übersicht über Mechanismus-Design, die zugrundeliegenden mathematischen Strukturen und beispielhafte Anwendungen. Zusammenhänge zu Markovschen Entscheidungsproblemen (MDP) sollen hergestellt werden. Eine mögliche weiterführende Aufgabe ist folgende: Für das Universitätskursstundenplanungsproblem sollen mögliche Einflussfaktoren des Mechanismus-Design erläutert werden, die aus dem Zusammenspiel von vielen Akteuren mit individuellen Interessen entstehen und Einfluss z. B. auf die Korrektheit von dezentral eingegebenen Daten haben können. Abgabe: 30.11.2010
- Peter Hoffmann (Diplomarbeit): Approximationsalgorithmen für das Lottyp-Designproblem Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter mit über tausend Filialen in Deutschland und Österreich. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl, wie z.B. 4 beschränkt.
Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
Bearbeitungszeitraum: 01.03.2010–31.10.2010 - Christopher Keim (Bachelorarbeit): Bender-Zerlegung des Universitätskursplanungsproblems. Im Universitätskursplanungsproblem geht es darum, Veranstaltungen Startzeiten und Räume zuzuweisen, derart, dass niemals zwei Veranstaltungen zur gleichen Zeit den selben Raum belegen und außerdem bestimmte Veranstaltungen nicht zeitgleich stattfinden. Aufgabe der Bachelor-Thesis ist es deshalb zu untersuchen, inwieweit sich dieses Problem durch Anwendung der Bender-Methode in ein Master- und ein Subproblem zerlegen lässt, um so auch realistische Instanzen lösen zu können. Abgabe: 31.07.2010
- Isabella Hoffmann (Bachelorarbeit): Konvergenz und Endlichkeit von Innere-Punkte-Verfahren für Lineare Programmierung. Bestimmte Innere-Punkte-Verfahren für die Lineare Programmierung sind sowohl theoretisch effizient als auch praxistauglich. Meistens werden diese Methoden in Bachelor-Vorlesungen nur in ihrer prinzipiellen Funktionsweise vorgestellt. Nachweise der Konvergenz oder Laufzeitkomplexitätsabschätzungen müssen dort ausgelassen werden. Aufgabe dieser Bachelorarbeit ist die Darstellung von primal-dualen Inneren-Punkte-Methoden zusammen mit dem Nachweis der superlinearen Konvergenz und der Endlichkeit (je nach Variante des Verfahrens). Abgabe: 31.07.2010
- Martin Schymalla (Diplomarbeit): Robuste Ganzzahlige Lineare Optimierung. Optimierung basiert in der Praxis auf Daten, die häufig nur geschätzt werden können. Beispiel: Kundennachfrage. Daher liefern deterministische Optimierungsmodelle oft Handlungsempfehlungen, die für die dann tatsächlich eintretenden Daten nicht unbedingt optimal sein müssen. Hat man keine Informationen über die stochastische Verteilung der Daten, so kann man mit Hilfe der robusten Optimierung dennoch eine im schlechtesten Fall optimale Lösung generieren. Aufgabe der Arbeit ist es, die Theorie der Robustifizierung von Optimierungsmodellen zu erläutern und diese in einem realen Fallbeispiel (optimierte Warenverteilung für einen Textildiscounter) anzuwenden. Dies beinhaltet Robustifizierung eines Modells, Datenerhebung, Implementierung und Testrechnungen sowie eine Diskussion der Ergebnisse im Vergleich zu szenariobasierter stochastischer Optimierung. Abgabe: 31.03.2010
- Stefan Baier (Zulassungsarbeit): Kombinatorik, Wahrscheinlichkeitsrechnung und Spieltheorie in der gymnasialen Mittelstufe anhand von Poker. Das Kartenspiel Poker erfreut sich seit einiger Zeit einer immer stärkeren Beliebtheit. Mittlerweile gibt es eine Reihe von Leuten, die von Siegprämien bei Pokertunieren leben können. Offensichtlich kann man Poker mehr oder weniger geschickt spielen. Dass Poker trotz Glücks- und Zufallskomponenten ein sehr strategisches Spiel ist, kann man u.a. daran sehen, wie viele Schachspieler sich mittlerweile, und sei es auch nur nebenbei, mit Poker beschäftigen. Der Schachgroß meister Matthias Wahls betreibt beispielsweise die Internetseite www.pokerstrategy.de.
Abgabe: 01.04.2010 - Katrin Dietrich (Zulassungsarbeit): Strukturisomere der Alkane. Chemische Verbindungen, welche die gleiche Summenformel aber unterschiedliche Verknüpfungen besitzen, werden Strukturisomere genannt. Eine Andersartigkeit in der Anordnung bzw. Verknüpfung führt teilweise zu abweichenden chemischen, physikalischen oder biologischen Eigenschaften. Ein Beispiel für eine Klasse chemischer Verbindungen sind die sogenannten Alkane (früher Paraffine). Dies sind gesättigte Kohlenwasserstoffe mit Summenformel CnH2n+2.
In vielen Chemiebüchern findet man Tabellen über die Anzahl der Strukturisomere von Alkanen aus n C-Atomen, siehe ggf. diese ausführliche Tabelle für bis zu 100 C-Atomen. Wie man auf diese Zahlen kommt wird dagegen nicht erwähnt.
Da die Verbindung der C-Atome bei Alkanen eine Baumstruktur besitzt, ist es hier noch relativ einfach die Anzahl der Strukturisomere zu berechnen bzw. die Strukturisomere computergeneriert zu erzeugen. Im Rahmen dieser Zulassungsarbeit sollten die notwendigen mathematischen und algorithmischen Grundlagen dargestellt werden.
Bearbeitungszeitraum: 22.06.2009–29.09.2009 - Matthias Lippert: Approximationsalgorithmen für Facility Location und K-Median Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl beschränkt.
Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
Bearbeitungszeitraum: 01.02.2009–31.07.2009 - Achim Hildenbrandt: Graphen mit Einheitsabständen. In der geometrischen Graphentheorie beschäftigt man sich mit Einbettungen von Graphen in die euklidische Ebene mit vorgegebenen Kantenlängen. Ein Spezialfall hiervon ist, dass alle Kanten Länge 1 besitzen. Anschulich können diese Graphen auch mit Streichhölzern gelegt werden. Im Rahmen dieser Diplomarbeit sollen z.B. Methoden entwickelt werden, mit denen man in vielen Fällen algorithmisch schnell zeigen kann, dass es für einen gegebenen Graphen keine Einbettung in die euklidische Ebene mit Einheitsabständen geben kann. Eine recht spezielle Frage ist, ob der sogennante Harborth-Graph der kleinste vierreguläre planare Graph mit Einheitskanten ist.
Bearbeitungszeitraum: 01.01.2009–31.07.2009 - Miriam Kießling: Ein Branch & Price-Verfahren zur optimierten Einsatzplanung von Winterdienstfahrzeugen. In einer vorangegangenen Arbeit, konnte ein Modell entwickelt werden, welches ermöglichte, die Gegebenheiten des Winterdienstes der Stadt Bayreuth abzubilden. Unter anderem ist dabei verlangt, dass bestimmte Straßen aufgrund einer gegebenen Priorität früher als andere geräumt werden müssen. Die Komplexität des resultierenden Modells macht es nötig, Verfahren anzuwenden, die über Standardlöser hinausgehen.
Aufgabe dieser Diplomarbeit ist es, das mathematische Modell für die Winderdiensteinsatzplanung aus der Vorläufer-Diplomarbeit in ein Branch & Price-Verfahren umzusetzen, zu analysieren, zu implementieren, auf realen Daten des Winterdienstes der Stadt Bayreuth zu testen und ggf. anzupassen.
Bearbeitungszeitraum: 01.10.2008–31.03.2009 - Nikolas Tautenhahn: Enumeration einfacher Spiele mit Anwendungen in der Stimmgewichtsverteilung, Mit Hilfe von sogenannten einfachen Spielen kann man Machtverhältnisse bei Abstimmungen mit Stimmgewichten beschreiben. Dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50\%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Die zugrunde liegende diskrete Struktur sind sogenannte Antiketten bzw. monotone boolsche Funktionen.
Aufgabe dieser Diplomarbeit ist es Verfahren weiter zu entwickeln, um einfache Spiele bis auf Isomorphie vollständig zu enumerieren.
Bearbeitungszeitraum: 01.04.2008–30.09.2008 - Anton Lastei: Machtindizes - Optimierung von Stimmgewichten, Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Sind die Stimmgewichte gegeben, so kann man den Machtanteil der einzelnen Länder über sogenannte Machtindizes ausrechnen. In der politikwissenschaftlichen Literatur lassen sich Analysen finden, wieviel Macht man einem Land in Abhängigkeit seiner Bevölkerungsgröße geben sollte, so dass kein Bewohner eines Landes übervorteilt wird. Diese Optimalverteilung gilt es mit ganzzahligen Stimmgewichten zu approximieren.
Aufgabe dieser Diplomarbeit ist es Verfahren zu entwickeln un zu implementieren, mit denen man dieses Optimierungsproblem in angemessener Zeit optimal oder inklusive einer Gütegarantie lösen kann.
Bearbeitungszeitraum: 01.04.2008–30.09.2008 - Tobias Kreisel: Optimierung von Patientenrouting und Ressourcen-Allokation in Krankenhäusern, Im Planungsprozess eines Krankenhauses sollen Optimierungspotentiale aufgespürt werden, die mit Methoden der Mathematischen Programmierung gehoben werden können. Allgemein sollen bei einer gegebenen Reihenfolge von Behandlungsschritten für einen Patienten mit einer bestimmten Einlieferungsdiagnose oder Terminbehandlung diese Schritte terminiert werden und sichergestellt werden, dass die für den jeweiligen Behandlungsschritt notwendigen Ressourcen pünktlich an Ort und Stelle sind (vereinfachter Spezialfall der Einbettung eines Patientenpfades in das Ressourcennetz des Krankenhauses, denn Patientenpfade können im Allgemeinen ganze Szenariobäume sein).
Aufgabe dieser Diplomarbeit ist die mathematische Modellierung dieser Patienten-Ressourcen-Termin-Zuordnung, die Entwicklung und Implementierung von Algorithmen zur Lösung der Modelle sowie Testrechnungen, möglichst auf Anwenderdaten.
Bearbeitungszeitraum: 01.12.2007–31.05.2008 - Constantin Gaul: Optimierte Warenverteilung für Textildiscounter, In einem Kooperationsprojekt mit dem Textildiscounter NKD Vertriebs GmbH stellt sich die folgende Aufgabe der optimalen Warenverteilung:
Gegeben sei eine Gesamteinkaufsmenge für einen Artikel; ferner gebe es Schätzungen für die fraktionale Nachfrage nach einem Artikel, und zwar für jede Konfektionsgröße und für jede der über Filialen; weiterhin sei noch eine Menge von erlaubten Lottypen gegeben; das sind Pakettypen, die angeben, wieviele Stück des Artikels von welcher Größe in ein Paket verpackt werden sollen; schließlich sei eine Höchstanzahl von verwendeten Lottypen für die Belieferung einer Filiale gegeben.
Gesucht ist nun für jeden erlaubten Lottyp die Anzahl der zu bestellenden Lots und für jede Filiale die Anzahl der zu liefernden Lots, so dass die Liefermenge möglichst wenig von der gegebenen frakionalen Nachfrage abweicht.
Aufgabe der Diplomarbeit ist es, mathematische Modelle und Algorithmen zu ihrer Lösung für die optimale Warenverteilung zu entwickeln, zu implementieren sowie theoretisch und experimentell zu analysieren.
Bearbeitungszeitraum: 01.11.2007–30.04.2008 - Konrad Schade: Lagerhaltungsstrategie für mehrstufige Lagerhaltung in der Automobilindustrie, Die Ersatzteilversorgung von Automobilwerkstätten muss schnelle Lieferzeiten garantieren und trotzdem wenig kosten. Um Lieferzeiten kurz zu halten, werden dezentrale Lager zur Belieferung der Werkstätten unterhalten, die ihrerseits von Zentrallägern beliefert werden. Momentan werden die Lagerhaltungspolitiken für alle Läger in dieser Hierarchie separat optimiert. Die vernetzte Lagerbestandskontrolle würde aber eine integrierte Optimierung der Lagerhaltungsstrategien aller Läger im Prinzip gestatten.
Aufgabe ist Modellierung, algorithmische Analyse, Implementierung und Test von Lagerhaltungsstrategien für mehrstufige Lagerhaltung.
Die Diplomarbeit wird in Zusammenarbeit mit der Volkswagen AG bearbeitet, für die die genannte Aufgabe wichtig ist.
Bearbeitungszeitraum: 01.11.2007–30.04.2008 - Susanne Zitzmann: Optimierte Einsatzplanung von Winterdienstfahrzeugen, Der Winterdienst der Stadt Bayreuth hat die Aufgabe, die wichtigsten Straßen in Bayreuth jeden Tag bis zu einer bestimmten, von der Priorität der Straße abhängigen Uhrzeit zu räumen und zu streuen. Das bedeutet, dass für die verfügbaren Räum- und Streufahrzeuge Touren geplant werden müssen, so dass alle Straßen einer jeden Prioritätsstufe jeweils rechtzeitig frei sind. Momentan werden diese Planungen vor der Winterzeit manuell durchgeführt.
Aufgabe dieser Diplomarbeit ist die mathematische Modellierung der Winterdiensteinsatzplanung, die Entwicklung und Implementierung von Algorithmen zur Lösung der Modelle sowie Testrechnungen auf Anwenderdaten. Letzteres erfordert auch die Mitwirkung bei der Datenerfassung des Praxispartners, denn wegen der Handplanung liegen nicht alle relevanten Daten in elektronisch verwertbarer Form vor.
Bearbeitungszeitraum: 01.12.2007–31.05.2008 - Shan Shan Hou: "Lotgrößenoptimierung bei einem Textildiscounter"
In einem Projekt zum Revenue-Management im Saisonwareneinzelhandel wurden Techniken entwickelt für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH größen- und filialgenauen Nachfragebedarf anhand historicher Daten zu schätzen. Die Belieferung der Filialen geschieht in Lots mit den Restriktionen, dass es insgesamt nur wenig verschiedene Lottypen geben darf, und dass eine einzelne Filiale sehr wenig verschiedene Lottypen bei einer Belieferung erhalten darf. Im Rahmen dieser Bachelorarbeit sollen exakte und heuristische Verfahren für die folgenden zwei Probleme untersucht und implementiert werden:
(1) Optimale Bestellpolitik von Lots bei gegebener Gesamtmenge und Bedarfsschätzung für die Filialen.
(2) Optimale Verteilpolitik von Lots bei gegebenen Lots und gegebener Nachfrageschätzung für die Filialen.
Bearbeitungszeitraum: 05.06.2007–04.08.2007 - Oskar Sommerfeldt: Nachtlinienplanung im ÖPNV unter Berücksichtigung von Fußwegen, Die Bayreuther Verkehrs- und Bäder-GmbH (BVB) erwägt eine Neuplanung der Nachtlinien für den Bayreuther ÖPNV mit dem Ziel, die Service-Qualität zu verbessern. Gute Service-Qualität für einen Passagier wird in der Literatur im Wesentlichen interpretiert als eine kleine Anzahl notwendiger Buswechsel und eine kurze Reisezeit.
In einem kleinen Verkehrsbetrieb wie dem BVB ist es unmöglich, mit dem Nachtliniennetz alle möglichen Haltestellen abzudecken. Daher werden für die meisten Fahrtwünsche Fußwege relevant.
Ziel dieser Diplomarbeit ist es, eine optimierte Linienplanung für die Nachtlinien der BVB auf Basis Ganzzahliger Linearer Optimierung (ILP) zu berechnen, die für die Fahrgastströme die Fußwege mit berücksichtigt.
Bearbeitungszeitraum: 01.01.2007–30.06.2007 - Iana Kouris: Dynamic Pricing for a Fashion Retailer, In einem Projekt zum Revenue-Management im Saisonwareneinzelhandel sollen für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH die dynamische Preisfestsetzung und die Belieferung der Filialen mit Konfektionsgrößen optimiert werden. Im Rahmen dieses Projektes müssen zunächst bekannte Verfahren der dynamischen Preisfestsetzung und der damit zusammenhängenden Modellierung des Nachfrageprozesses auf ihre Eignung im Projekt untersucht werden.
Bearbeitungszeitraum: 01.02.2007–31.07.2007 - Christoph Wopperer: Optimierung der Preisreduzierungsstrategie eines Textildiscounters, In einem weiteren Projekt zum Revenue-Management im Saisonwareneinzelhandel sollen für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH die dynamische Preisfestsetzung und die Belieferung der Filialen mit Konfektionsgrößen optimiert werden. Im Rahmen dieses Projektes müssen diskrete Verfahren zur optimalen Preisfestsetzung untersucht werden, da Preisreduzierungen nur zu festen Zeiten und auf feste Preisstufen möglich sind.
Bearbeitungszeitraum: 01.11.2006–30.04.2007 - Stefanie Sutter: Optimale Mischung von Sanden unter unsicherer Lagerinformation
Die Firma LivingLogic optimiert derzeit die Mischung von Sanden nach Kundenwunsch für die Firma Strobel Quarzsand GmbH (mehr). Die dabei zu lösende Aufgabe lautet: eine durch den Kundenwunsch gegebene Körnungsverteilung (inklusive Toleranzen und Gewichtungen) soll durch Mischung von Sanden aus 30 Silos mit bekannten Körnungsverteilungen möglichst gut approximiert werden. In dieser Diplomarbeit soll untersucht werden, ob mit Methoden der Stochastischen Dynamischen Programmierung oder der Online-Optimierung ein bzgl. unvorhergesehener Ereignisse robusteres Verfahren geschaffen werden kann bzw. mathematische Gütekriterien angegeben werden können.
Bearbeitungszeitraum: 30.03.2006–29.09.2006 - Manuela Mosburger: Spieltheorie – Eine anschauliche Einführung mit anwendungsbezogenen Beispielen aus Ökonomie und Alltag
Die Methoden der Spieltheorie können bei vielen praktischen Problemen auftreten. Sie gibt Antworten auf Fragen wie, "Warum ist es bei der Verkehrsplanung nicht immer besser, zusätzliche Straßen zu bauen?" oder "Warum nähern sich die großen politischen Parteien mit ihren Konzepten so stark an?". Im Rahmen einer Zulassungsarbeit soll anhand einer zu entwickelnden anschaulichen Einführung in die Spieltheorie aufgezeigt werden, dass dieses Thema auch für den Schulunterricht geeignet ist. Folgerungen aus der Anschaung heraus sollen das sonst häufig vertretene Satz-Beweis-Prinzip ersetzen. Abgerundet wird die Arbeit durch Darstellungen von Problemen aus der Praxis.
Bearbeitungszeitraum: ?–Oktober 2006 - Cornelius Schwarz: Subgradientenmethoden zur dynamischen Spaltengenerierung für die echzeitfähige Einsatzplanung von Pannenhilfefahrzeugen
In einem Projekt zur Einsatzplanung von Pannenhilfefahrzeugen des ADAC ist am ZIB ein echtzeichfähiger Reoptimierungsalgorithmus auf Basis ganzzahlige Programmierung entwickelt worden. Dieser beruht auf dynamischer Spaltengenerierung zur Erzeugung von möglichst wenig chancenreichen Tourvariablen. Thema der Diplomarbeit ist bestehende Iteration eines linearen Programms zur Spaltengenerierung mit einem Verfahren aus der nicht-differenzierbaren Optimierung zu vergleichen.
Bearbeitungszeitraum: 01.01.2006–30.06.2006 - Tobias Schneider: Optimierte Auslastung von Laserquellen im Automobilkarosseriebau
Laserschweißen hat sich während der letzten 10 Jahre zu einer Schlüsseltechnologie im Karosseriebau entwickelt. Hierbei werden mehrere Schweißroboter von einer gemeinsamen externen Laserquelle versorgt. Ziel eines gemeinsamen Projekts mit dem ZIB ist es, die bestmögliche Auslastung der teuersten Resource, der Laserquellen, zu erreichen. Thema der Arbeit ist die Modellierung sowie der Entwurf und die Analyse von Algorithmen für ein abgeleitetes Scheduling-Problem.
Bearbeitungszeitraum: 01.11.2005–30.04.2006 - Stefan Tuffner: Iteriertes Assignment vs. Reoptimierung zur Fahrzeugeinsatzplanung
Die Einsatzplanung der Hilfefahrzeuge des ADAC geschieht bereits in vier Hilfezentralen mit Hilfe einer Echtzeit-Reoptimierung auf Basis Ganzzahliger Linearer Programmierung. Als konkurrierender heuristischer Ansatz wird häufig die Methode des iterierten Assignments verwendet, um den Aufwand der exakten Reoptimierung zu vermeiden. Ziel dieser Arbeit ist der Vergleich der existierenden Reoptimierung mit dem iterierten Assignment sowohl auf konstruierten Beispielinstanzen als auch auf realen Daten des ADAC.
Bearbeitungszeitraum: 28.10.2005–28.04.2006 - Simone Schuler: Lineare Optimierung in der Schule
Die Lineare Optierung ist aus der betriebswirtschaftlichen Praxis nicht mehr wegzudenken. Im Rahmen einer Zulassungsarbeit soll anhand einer zu entwickelnden anschaulichen Einführung in die Lineare Optimierung aufgezeigt werden, dass dieses Thema auch für den Schulunterricht geeignet ist. Folgerungen aus der Anschaung heraus sollen das sonst häufig vertretene Satz-Beweis-Prinzip ersetzen. Abgerundet wird die Arbeit durch Darstellungen von Optimierungsproblemen aus der Praxis.
Bearbeitungszeitraum: ?–?
