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
- 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
- Janett Eibisch (Masterarbeit): Berechnung von Hammingabständen mit ganzzahliger linearer Optimierung. In vielen Produkten sind informationsverarbeitende Systeme integriert. Die enorme Steigerung der Performanz und Flexibilität dieser Systeme begünstigt dabei den Anstieg der Komplexität. So werden durch Steuerungen letzlich auch Aktionen durchgeführt, welche Personen in der Umgebung potentiell Schaden zufügen können. Das Themengebiet der Sicherheit beschäftigt sich mit der Fragestellung, welche Maßnahmen getroffen werden müssen, damit aus einem unerwarteten Verhalten des betrachteten Systems keine Gefahrensituation entstehen kann. Diese sogenannten Sicherheitsfunktionen werden i.d.R. durch sichere Messaufnehmer, Kommunikationseinrichtungen, Steuerungen bzw. Aktoren realisiert. Häufig kommen hier kostenintensive redundante Hardware-Strukturen zum Einsatz. Moderne Steuerungen verwenden arithmetische Codes zur Fehleraufdeckung. Als deterministische Kriterien zur Bewertung der Fehleraufdeckung werden beispielsweise die arithmetische Distanz und die minimale Hamming Distanz betrachtet. In Sicherheitsnachweisen müssen die entsprechende Werte gegenüber unabhängigen Gutachtern (TÜV, IFA, ...) nachgewiesen werden.
Im Rahmen dieser Masterarbeit soll untersucht werden, wie die Bestimmung der Hamming Distanz bei arithmetischen Codes als ganzzahliges lineares Programm formuliert und mit den zugehörigen Methoden gelöst werden kann.
Abgabe: 31.07.2015 - Nils Olsen (Masterarbeit): Optimale Terminvereinbarung unter Unsicherheit: Ein Vergleich verschiedener mathematischer Modellierungsansätze. Motiviert durch die Fragestellung, wie man am besten die Kunden-Termine für Service-Techniker vereinbart, um trotz ungewisser zukünftiger Nachfragen Service-Qualität hoch und Kosten niedrig zu halten, wurde in [5] als allgemeiner Rahmen das stilisierte mathematische Optimierungsproblem Online Target Date Assignment (OnlineTDAP) eingeführt und mit Hilfe kompetitiver Analyse untersucht. Diese Art der Analyse ist nur ein möglicher Zugang zur fundierten Entscheidungsfindung unter unsicheren Informationen. Ansätze der stochastischen oder robusten Optimierung sowie eine Modellierung als stochastisches dynamisches Entscheidungsproblem kommen genauso in Frage. Sehr selten nur werden diese Modellierungs-Paradigmen anhand eines gemeinsamen Beispiels verglichen.
Aufgabe dieser Masterarbeit ist es, geeignete Varianten des Online Target Date Assignment Problems mit stochastischer/robuster/dynamischer Optimierung zu modellieren und daraus resultierende Handlungsempfehlungen zu vergleichen.
Abgabe: 30.09.2014 - Clarissa Reim (Bachelorarbeit): Optimierung von Kurierdiensten unter Unsicherheit. Die Optimierung der Auslieferfahrten von Kurierdiensten kann man im weiteren Sinne als Vehicle Routing Problem (VRP) modellieren. Eine deterministische Modellierung findet aber oft Lösungen, die bei einer Änderung/Ergänzung der Daten gar nicht mehr gut sein müssen. Eine mathematische Modellierungsmöglichkeit ist die Stochastische Ganzzahlige Lineare Optimierung mit Kompensation (SILP). Aufgabe dieser Bachelorarbeit ist es, das Modell aus [2] zu erläutern und mit Beispielen das Verhalten in Bezug auf Störungen zu illustrieren.
Abgabe: 31.08.2014 - Tina Trautner (Bachelorarbeit): Branch-and-Cut für Universitätskurs-Stunden- und Raumplanung. Universitätskurs-Stunden- und Raumplanung (UCT) kann mit Hilfe Ganzzahliger Linearer Programmierung (ILP) modelliert werden. An der Universität Bayreuth ist dieser Ansatz in einem von der Oberfrankenstiftung geförderten Forschungsprojekt (AZuR) verfolgt worden. Die Lösung der entstehenden ILPs für realistische Problemgrößen erfordert fortgeschrittene Techniken. Während in AZuR hauptsächlich dynamische Spaltengenerierung verfolgt wurde, ist es das Ziel dieser Bachelor-Arbeit, Schnittebenen-Methoden und ihre Integration in einen Branch-and-Bound-Algorithmus, also Branch-and-Cut-Verfahren (B&C) zu beleuchten. Hierbei werden schwierig zu behandelnde Klassen von Nebenbedingungen oder implizierte Restriktionen nicht vollständig zum Modell hinzugefügt, sondern nach und nach separiert.
Abgabe: 31.07.2014 - Lisa Bauer (Bachelorarbeit): Effiziente Minimierung der Bestrahlungsdauer in der Krebstherapie mit Linearer Programmierung. Um bei der Bestrahlung von Tumoren möglichst wenig gesundes Gewebe zu beeinträchtigen, werden in Bestrahlungsgeräten Blenden eingesetzt. Die Planung der Bestrahlung besteht dann aus einem therapeutisch gewünschten Blendenmuster und einer Abfolge von durch das Gerät realisierbaren Blendenmustern, die sich zum gewünschten zusammensetzen. Je nachdem, wie man ein gewünschtes Muster zusammensetzt, wird der Patient unterschiedlich lange der Bestrahlung ausgesetzt. Das Optimierungsproblem, unter allen Zusammensetzungen die mit der geringsten Gesamtbestrahlungsdauer zu finden, kann man als Lineares Programmn (LP) mit sehr vielen Variablen modellieren. Aufgabe dieser Bachelorarbeit ist es, zu erklären, auf welche Weise diese Lineare Programm in Polynomialzeit zu lösen ist, und zu untersuchen, ob es nicht auch ein Lineares Programm mit polynomiell vielen Variablen gibt.
Abgabe: 31.07.2014 - Madeleine Löhnert (Bachelorarbeit): Lot-Type-Design: Kompakte versus extensive Modellierung. Das Lot-Type-Design-Problem (LDP) fragt nach der besten Auswahl einer kleinen Menge von Vorverpackungstypen für verschiedene Größen eines Mode-Artikels (Lot-Typ) zur Belieferung einer großen Anzahl von Filialen. Ein Lot-Typ ist gegeben durch eine Anzahl für jede Konfektionsgröße. Die Bedeutung: Ein Lot dieses Typs ist eine Folientasche, die die im Lot-Typ angegebene Anzahl von Artikeln in jeder Größe enthält. Die Belieferung jeder Filiale erfolgt über eine Anzahl von Lots eines der ausgewählten Lot-Typen. Die Bewertung eines Lot-Designs erfolgt über den Abstand der resultierenden Stückzahlen in den Filialen mit ihren vorgegebenen, deterministischen Nachfragen. Diese Aufgabe trat auf im Rahmen des von der Bayerischen Forschungsstiftung geförderten Projekts DISPO in Zusammenarbeit mit einem Textildiscounter vom LS Wirtschaftsmathematik in Kooperation mit dem LS BWL V (Prof. Dr. J. Schlüchtermann). Um das LDP als Ganzzahliges Lineares Programm (ILP) zu formulieren, kann man entweder eine Anzahl-Variable für jede Größenposition eines Lot-Typen (kompaktes Modell) oder eine Auswahlvariable für jeden Lot-Typen (extensives Modell) ansetzen. Aufgabe dieser Bachelor-Arbeit ist es, die beiden Modellierungsansätze in Bezug auf Modellgröße, Ganzzahligkeitslücke und mögliche Lösungsverfahren zu vergleichen.
Abgabe: 31.07.2014 - Lena Reinl (Bachelorarbeit): Approximationsalgorithmen für das Handlungsreisendenproblem. Das Handlungsreisendenproblem (TSP) fragt nach der kürzesten Rundreise durch eine endliche Menge von Städten. Das das Problem einerseits NP-schwer ist und andererseits als Modell auf viele Anwendungen passt, sind effiziente Approximationsalgorithmen mit garantierter Lösungsqualität interessant. Berühmt ist der Christofides-Algorithmus für das metrische TSP, der stets eine Tour mit einer Länge von höchstens 3/2 mal der optimalen Tourlänge in Polynomialzeit ermittelt. Aufgabe der Bachelorarbeit ist es, die neueren Entwicklungen bei Approximationsalgorithmen für das TSP zu beleuchten und ein ausgewähltes Ergebnis dabei detaillierter zu studieren.
Abgabe: 31.07.2014 - Franziska Eisenhuth (Bachelorarbeit): Heuristiken, Schranken und exakte Algorithmen für Graphenfärbung. Graphenfärbung gehört zu den klassischen NP-schweren kombinatorischen Optimierungsproblemen. Jedem Knoten eines ungerichteten Graphen muss dabei so eine Farbe zugeordnet werden, so dass die Endknoten jeder Kante stets unterschiedliche Farben haben. Ziel ist die Minimierung der Anzahl benötigter Farben. Es gibt in der Literatur sowohl exakte Modelle der Ganzzahligen Linearen Optimierung (ILP) als auch verschiedenste Heuristiken. Aufgabe dieser Bachelorarbeit ist es, einen Überblick über die verschiedenen Ansätze zu verfassen mit dem Fokus auf einer selbst gewählten Methode, die etwas detaillierter beschrieben werden soll.
Abgabe: 31.07.2014
Abgeschlossene Bachelorarbeiten
- Nadja Catizone (Bachelorarbeit): Losgrößenoptimierung mit Gemischt-Ganzzahliger Programmierung. Das Ziel der Losgrößenoptimierung ist die Bestimmung von bestmöglichen Bestellmengen zu festen Zeitpunkten bis zu einem festgelegten Zeithorizont. Im deterministischen Fall sind die Nachfragemengen und Lieferzeiten vorgegeben. Meistens sollen die Gesamtkosten bestehend aus Bestellkosten, Lagerhaltungskosten, Lieferverzögerungskosten minimiert werden. Verschiedene Nebenbedingungen sind denkbar wie Kapazitätsrestriktionen für Produktionseinheiten oder Lieferanten.
In dieser Bachelor-Arbeit sollen Methoden für Losgrößenbestimmung dargestellt werden, mit besonderem Augenmerk auf Gemischt-Ganzzahligen Optimierungs-Modellen (MILP). Hier soll insbesondere die Frage untersucht werden, inwieweit durch Auftreten anderer als der vorhegesagten Nachfragen die Entscheidungsvorschläge des MILP-Modells zu schlechtem Gesamtverhalten führen können.
Mathematische Strategien, um das Problem mit volatiler Nachfrage zu lösen, sollen kurz skizziert und diskutiert werden.
Abgabe: 31.12.2013 - Andreas Deuerling (Bachelorarbeit): Entwurf und Analyse von Spaltengeneratoren für das Universitätskursstundenplanungsproblem. In einer Veröffentlichung von 2005 schlagen Qualizza und Serafini einen Ansatz zur Lösung des Universitätskursstundenplanungsproblems vor, der auf dynamischer Spaltengenerierung basiert.
Gegenstand dieser Bachelorarbeit ist es, die in [1] erwähnten Methoden zur Generierung einzelner Spalten zu untersuchen und weitere zu entwerfen.
Abgabe: 28.02.2013 - Martin Friedel (Bachelorarbeit): k-Fence Ungleichungen für das Laserschweißproblem. Beim Laserschweißproblem mit festen Touren (LSP-T) [4, 5] teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist.
Abgabe: 31.09.2012 - Thomas Ippisch (Bachelorarbeit): Das Stacker Crane Problem mit Kapazitäten. Das Stacker Crane Problem (SCP) fragt nach einer Sortierung von Ein- und Auslageraufträgen eines Regalbediengeräts (RBG) der Kapazität C = 1 mit minimaler Gesamtleerfahrtstrecke.
Thema dieser Bachelor-Arbeit ist es, das SCP mit Kapazitäten C > 1 und in Anbetracht geeigneter Regeln für die Abfolgen von Ein- und Auslagerungen algorithmisch zu untersuchen. RBG mit C > 1 gibt es für Kartons, während die RBG mit C = 1 meist für Euro-Paletten gedacht sind. Zusätzliche Regeln können sein: Alle zur Einlagerung aufgenommenen Kartons müssen eingelagert sein, bevor die erste auszulagernde Palette aufgenommen wird. Ferner ist die Be- und Entladung dieser RBG üblicherweise nicht in beliebiger Reihenfolge möglich.
Abgabe: 31.08.2012 - Thomas Blos (Bachelorarbeit): Heuristiken für das Asymmetrische Traveling Salesman Problem. Das Traveling Salesman Problem (TSP) fragt nach einer kürzesten Rundreise durch n Städte. Das TSP gehört zur Klasse der NP-schweren Probleme. Daher sind auch Heuristiken und Approximationsalgorithmen von Interesse. Für das metrische TSP gibt es den 3/2 -Approximationsalgorithmus von Christofides. Für das symmetrische TSP ist die Lin-Kernighan-Heuristik eine in der Praxis bewährte Methode.
Thema dieser Bachelor-Arbeit ist es, ähnliche Heuristiken und/oder Approximationsalgorithmenfür das asymmetrische TSP zusammenzustellen und auf Beispiel-Instanzen zu testen.
Abgabe: 31.08.2012 - Cornelia Strube (Bachelorarbeit): Dimensionsreduktion für ökologische Daten mit linearer und quadratischer ganzzahliger Programmierung. Im Verfahren Isomap des Lehrstuhls für ökologische Modellbildung werden Umweltdaten durch Einbettung in einen diskreten metrischen Raum und nachfolgender Dimensionsreduktion analysiert. (Siehe Anlage.)
Aufgabe der Bachelor-Arbeit ist Beschreibung und der Test verschiedener mathematischer Modelle für Metriken und Optimalität der Dimensionsreduktion und entsprechender Rechenverfahren. Insbesondere sollen die Optimallösungen bzgl. verschiedener Normen (euklisisch, Betragssummennorm) im Hinblick auf Robustheit gegenüber Daten-Ausreißern untersucht werden.
Abgabe: 31.07.2012 - Martin Kolenda (Bachelorarbeit): Varianten des Assignment-Problems mit Anwendungen in der Universitäts-Raumplanung. In einem von der Oberfrankenstiftung geförderten Forschungsprojekt (AZuR) soll u. a. ein Optimierungsverfahren entwickelt werden, dass Veranstaltungssitzungen Zeiten und Räume so zuweist, dass bestimmte Nebenbedingungen erfüllt sind (keine Überschneidungen, Doppelstunden aufeinanderfolgend u. v. a. m.). Ein Teilproblem ist die Zuweisung von Räumen für Veranstaltungen. In der einfachsten Form (alle Veranstaltungen sind nur eine Zeiteinheit lang; keine weitere Nebenbedingungen) kann das Raumzuweisungsproblem als ein Assignment-Problem formuliert werden.
Da das aktuelle Gesamt-Modell auf einem Stundenraster arbeitet, aber die meisten Veranstaltungen Doppelstunden benutzen, sollte bei der Raumzuweisung für eine Doppelstunde kein Raumwechsel vorgenommen werden. Das lässt sich nicht (zumindestens nicht ohne Tricks) als ein elementares Assignment-Problem modellieren.
Aufgabe der Bachelor-Arbeit ist es, Vorschläge für graphentheoretische Raumzuweisungsmodelle zu machen, die das Doppelstunden-Raumwechselverbot und evtl. ähnliche Praxisbedingungen mit einbezieht. Ferner soll untersucht werden, inwiefern sich Standard-Assignment-Algorithmen auf die neuen Modelle verallgemeinern lassen. Insbesondere ist der Komplexitätsstatus der verallgemeinerten Assignment-Probleme von Interesse.
Abgabe: 31.07.2012 - 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 - 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
- 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
Abgeschlossene Masterarbeiten
- Daniel Heinlein (Masterarbeit): Netzwerkcodes. Netzwerkcodes stellen ein Verfahren zur Verfügung, Daten mit der Möglichkeit, Übertragungsfehler zu korrigieren, zu kodieren. In dieser Arbeit sollen sogenannte constant dimension codes, eine Form dieser Netzwerkcodes, mit Techniken der ganzzahligen linearen Optimierung untersucht werden. Ziel ist es möglichst große Codes zu finden. Diese sind wichtig, da größere Codes weniger zusätzliche Daten erfordern, um die gleiche Anzahl an Ausgangsdaten zu kodieren.
Abgabe: 19.07.2014 - Susanne Börner (Masterarbeit): 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.
Abgabe: 28.02.2014 - 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
Abgeschlossene Zulassungsarbeiten
- 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 - 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 - 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: ?–?
Abgeschlossene Diplomarbeiten
- 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 - Nadine Geiß (Diplomarbeit): Lokale Politik-Evaluierung für Paging. Die Berechnung optimaler Politiken für diskontierte Markovsche Entscheidungsprobleme mit unendlichem Horizont ist für interessante Problem oft nicht möglich wegen zu großer Zustandsräume. In [5] wird ein Verfahren beschrieben, wie man mit der LP-Methode und dynamischer Spaltengenerierung trotzdem noch rigorose Informationen über die Qualität von gegebenen Politiken in Bezug auf eine unbekannte optimale Politik gewinnen kann. Auf der anderen Seite gibt es Online-Probleme, für die kompetitive Analyse nur ein schwaches Entscheidungskriterium für die Auswahl von Politiken liefert.
Aufgabe dieser Diplomarbeit ist es, dieses Verfahren auf das typische Online-Problem ”Paging“ und die gängigen Politiken anzuwenden.
Abgabe: 31.10.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 - Debora Berger (Diplomarbeit): Gültige Ungleichungen des Linear Ordering Polytopes für das Laserschweißproblems Beim Laserschweißproblem mit festen Touren (LSP-T) teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist.
Aufgabe der Diplomarbeit ist zu untersuchen, ob sich für das Linear Ordering Polytope gültige Ungleichungen zur Lösung des Laserschweißproblems verwenden lassen. Abgabe: 31.12.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
- 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
- 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
- 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): 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
- 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 - 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
- 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 - Matthias Lippert (Diplomarbeit): 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 - 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 - Paul Göpfert (Diplomarbeit): Ganzzahlige Polynomiale Programmierung auf Basis algebraischer Strukturen. Nicht-standard-Ansätze in der Ganzzahligen Optimierung auf Basis algebraischer Strukturen sind trotz ihres beweisbar effizienten Laufzeitverhaltens in fester Dimension im industriellen Umfeld bislang noch nicht konkurrenzfähig. In Einzelfällen sind sie aber besser geeignet als die Standard-Branch- and-Bound-Verfahren. Vor allem bieten sie aber mehr Möglichkeiten der Verallgemeinerung auf nicht-lineare Probleme. Ein erstes Resultat in dieser Richtung wurde vor kurzem in [2] vorgestellt: Ein voll-polynomiales Approximationsschema für polynomiale gemischt-ganzzahlige Programmierung in fester Dimension.
In dieser Arbeit sollen die Hintergründe, Ideen und Strukturen, die zu diesem Resultat geführt haben, erläutert werden. Ferner soll das tatsächliche Verhalten durch Implementierung und Testrechnung untersucht werden.
Bearbeitungszeitraum: 24.06.2008–23.12.2008 - 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 - 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 - 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 - Iana Kouris (Diplomarbeit): 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 - 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 - Christoph Wopperer (Diplomarbeit): 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 - 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 (Diplomarbeit): 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 (Diplomarbeit): 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
