Abschlussarbeiten

Sie möchten Ihre Abschlussarbeit in Operations Research oder mathematischer Optimierung schreiben? Hier finden Sie Themen und Wissenswertes.

108
Abschlussarbeiten

Das Wichtigste in Kürze

Sie studieren Mathematik, Informatik, Data Science, Wirtschaftswissenschaft, Wirtschaftsingenieurwesen oder BWL. Sie haben sehr gute Kenntnisse in Operations Research oder mathematischer Optimierung, z.B. aus unseren Kursen und Seminaren. In der Regel können Sie gut programmieren. Sie schreiben Ihre Arbeit auf deutsch oder englisch und natürlich in LaTeX. 

Inhaltlich kann es um die theoretische/strukturelle Analyse/Verbesserung von Optimierungsproblemen/-algorithmen gehen, und/oder um deren Modellierung/Implementation und/oder deren experimentelle Auswertung. Bei der Lösung praktischer Optimierungsaufgaben bearbeiten Sie im Allgemeinen den gesamten OR Prozess. Sind Sie an einem praktischen Optimierungsproblem interessiert, haben Sie unsere "praktische Optimierung" gehört, vielleicht auch ein OR Praktikum mitgemacht.

Sind Sie speziell an Branch-and-Price, insbesondere an GCG interessiert oder der Verbindung von Optimierung und Machine Learning, finden wir immer ein Thema für Sie. Wenn Sie Ihr eigenes Thema mitbringen oder etwas Anderes suchen als unten aufgelistet ist, kontaktieren Sie Marco Lübbecke.

 

Themen offener Abschlussarbeiten

0
A Hierarchy of Dantzig-Wolfe Decompositions
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Im Artikel

Bastubbe, M., Lübbecke, M. and Witt, J.T.
A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

 

ermitteln wir experimentell für "alle" möglichen Dantzig-Wolfe Reformulierungen eines (kleinen) ganzzahligen Programms die Stärke der resultierenden dualen Schranke. Dazu nehmen wir alle (exponentiell) vielen Teilmengen von Restriktionen, reformulieren die jeweilige Teilmenge und berechnen die Schranke. Man könnte erwarten, dass man dabei sehr viele verschiedene (im Extremfall wiederum exponentiell viele) verschiedene Werte für die duale Schranke findet. Interessanterweise ist das nicht so, ganz im Gegenteil sind es nur sehr, sehr wenige verschiedene Werte. Der Grund ist, dass viele verschiedene Dekompositionen auf dieselbe duale Schranke führen und die Frage ist: warum? Wir vermuten im Ausblick obiges Artikels, dass sich sehr wenige "Repräsentaten" gibt, die dann eine "Hierarchie" (immer stärkerer) Dekompositionen bilden (von der LP Relaxation bis zur ganzzahligen Hülle).

In dieser Arbeit soll dieser Vermutung experimentell und theoretisch nachgegangen werden.

A Python Interface to GCG
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Wir entwickeln den quelloffenen Löser GCG für strukturierte ganzzahlige Programme (und wenn Sie dieses Thema bearbeiten möchten, sind Sie sehr wahrscheinlich schon damit in Berührung gekommen). GCG basiert auf dem SCIP Framework, für das es (neben anderen Sprachen) eine C/C++ API gibt, sowie eine Python API, die sich PySCIPOpt nennt. Im Rahmen dieser Arbeit soll dieses Python Interface auf GCG erweitert werden. Sie müssen sich gut mit ganzzahliger Optimierung, Dantzig-Wolfe Reformulierung, Column Generation und Branch-and-Price auskennen. Vor allem ist dieses Thema aber eines der guten Software-Entwicklung. Die bestehende C/C++ API muss (natürlich mit unserer Hilfe) überarbeitet werden, um dann die wichtigsten Methoden in einer (Weiterentwicklung von PySCIPOpt als) Python API zur Verfügung zu stellen. Die neue Schnittstelle sollte mit einem Beispielprojekt exemplarisch beschrieben werden.

Die Python API ist das nachgefragteste Feature von GCG und die wissenschaftliche Community würde ihren auf ewig dankbar sein.

Approaches for solving Hub Location Problems (and variants)
Abschluss: B.Sc. / M.Sc.
Kontakt: A. Helber
Details

In der Logistik und der Telekommunikation spielen Hub Location Probleme eine Schlüsselrolle bei der Gestaltung des Netzlayouts. Obwohl umfangreiche Forschungsarbeiten zur Lösung dieses Problems und seiner Varianten durchgeführt wurden, sind große Instanzen der Lehrbuchvariante und sogar kleine Instanzen etwas komplexerer Varianten nach wie vor schwer zu lösen. Wir arbeiten derzeit gemeinsam mit DHL Freight an einem Hub Location Problem im Stückgutverkehr, das sowohl große Instanzen als auch potenziell recht komplex Modelle umfasst. Dies kann als spezifische Anwendung für die in dieser Arbeit entwickelten Methoden dienen, aber die Lösung des Praxisproblems steht nicht im Mittelpunkt.

Themen, die für die Lösung von Hub Location Problemen von Interesse sein könnten, sind:

- Implementierung und mögliche Verbesserung von exakten State-of-the-Art Methoden, z.B. in den Open-Source-Solvern SCIP oder GCG.
- Implementierung bestehender und Entwicklung neuer Heuristiken.
- Entwicklung und Implementierung von Aggregationsmethoden zur Reduzierung der Instanzgrößen.
- Analyse der aktuellen Transportvorgänge zur formalen Beschreibung der relevanten Aspekte, die berücksichtigt oder vereinfacht werden könnten. Darauf aufbauend werden verschiedene Modelle zur Darstellung der Transportvorgänge mit Hilfe von Off-the-Shelve-Solvern implementiert und rechnerisch im Hinblick auf Lösungszeiten und Realitätsnähe bewertet.

Alle Themen erfordern Rechenstudien, um die Leistung der implementierten Methoden zu bewerten und zu vergleichen. Theoretische Beiträge sind ebenfalls willkommen. Kenntnisse in kombinatorischer Optimierung und Programmierung (vorzugsweise in C/C++, Python oder Julia) sind erforderlich. Bei Interesse schildern sie bitte kurz ihre Vorkenntnisse sowie Themen und Methoden die sie interessieren und hängen sie ihren Notenspiegel an.

Branch-and-Price Applications: Improving on the Literature
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Wir sehen häufig Veröffentlichungen zu Optimierungsaufgaben in Wissenschaft und Praxis, in denen mit ganzzahligen Programmen modelliert wird. Oft liegt eine andere Modellierung nahe, die auf eine Lösung mit Column Generation und Branch-and-Price führt, aber von den Autoren nicht gemacht wurde. In Ihrer Abschlussarbeit beschäftigen Sie sich mit so einem Modell, überlegen sich eine alternative Modellierung, wie Master- und das Pricing-Problem aussehen müssen, welche Algorithmen hierfür in Frage kommen, welche problemspezifischen Beschleunigungen nutzbar sind, implementieren alles in SCIP oder idealerweise direkt in GCG und vergleichen Ihren neuen Ansatz experimentell mit dem bestehenden in der Literatur. Theoretische Überlegungen dazu wie Komplexitätsuntersuchungen, Ausnutzen kombinatorischer Strukturen etc. sind gerne dabei gesehen. Eine sehr runde Sache.

Branching in Branch-and-Price: An experimental Study
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Wir entwickeln am Lehrstuhl den generischen Branch-and-Price Löser GCG. In diesem sind klassische Branching-Regeln implementiert wie Branching auf Originalvariablen, Ryan-Foster Branching für Set Partitoning Probleme und auch Vanderbeck's generisches Branching. Es gibt in der Literatur noch keinen allgemeinen experimentellen Vergleich solcher Branching-Regeln im Kontext von Branch-and-Price. Dieser soll im Rahmen der Arbeit durchgeführt werden. Dazu konzipieren und implementieren Sie weitere Regeln aus der Literatur, z.B. Strong Branching, führen Experimente zur Performance der einzelnen Regeln durch, z.B. welchen Einfluss die Zeilenwahl bei Ryan-Foster Branching hat und wie eine geschickte Wahl auszusehen hat und vergleichen abschließend in einer großen Rechenstudie die Vorschläge.

Covering Integer Programs for Rectilinear Picture Compression
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

In dieser Arbeit soll nach Optimierungsmodellen und -algorithmen gesucht werden, mit deren Hilfe sich einfarbige digitale Bilder verlustfrei oder verlustbehaftet komprimieren lassen. Die Pixel eines Bildes lassen sich z.B. mit Rechtecken oder anderen "Formen" überdecken. Dies mit einer minimalen Anzahl geeigneter Formen zu tun, macht die Aufgabe zu einem Optimierungsproblem. Erste Ansätze finden sich etwa hier. Möglicherweise muss bei der Auswahl zu verwendenden "Formen" ein Column Generation Ansatz verfolgt werden, was die Aufgabe auch algorithmisch spannend macht. Natürlich bietet dieses Thema reichlich Raum für Implementation und (anschauliche) Experimente.

Dantzig-Wolfe reformulation of the conflict graph
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Löser für ganzzahlige Programme nutzen viele Modellinformationen aus, z.B. den Konfliktgraphen, der für Binärvariablen(werte) Knoten enthält und Kanten zwischen diesen, wenn die entsprechenden Wertebelegungen eine Unzulässigkeit erzeugen würden. Der Graph lässt sich direkt erzeugen und im Laufe des Löseprozesses gewonnene Informationen werden laufen hinzugefügt. Cliquen in diesem Graphen führen auf starke gültige Ungleichungen, die dem Modell automatisch hinzugefügt werden.

In dieser Abschlussarbeit soll evaluiert werden, die stark die gültigen Ungleichungen bestenfalls sind. Dazu wird eine bestimmte Dantzig-Wolfe Reformulierung angewendet, die im Wesentlichen die Stable Set Formulierung des Konfliktgraphen im Subproblem hat. Dadurch gewinnt man implizit alle möglichen gültigen Ungleichungen aus dem Stable Set Polytop, nicht nur die Clique-Ungleichungen.

Diese Algorithmik soll in unserem Löser GCG umgesetzt und experimentell evaluiert werden.

Detecting staircase structure in integer programming models
Abschluss: B.Sc. oder M.Sc.
Kontakt: M. Lübbecke
Details

Ganzzahlige Programme enthalten oft eine (Modell)struktur, die man algorithmisch ausnutzen kann, z.B. mit unserem Löser GCG. Eine in Modellen häufig auftretende Stuktur ist die sog. Treppenstufenform, die man immer dann antrifft, wenn z.B. Entscheidungen in mehreren aufeinander folgenden Zeitperioden getroffen werden müssen (wie etwa in der Lagerhaltung). Die Koeffizientenmatrizen solcher Modelle kann man so umordnen, dass eine Form wie folgt entsteht:

staircase structure in a matrix

Solche Formen können mit Graphenalgorithmen erkannt werden. Man sieht recht deutlich die Kopplung zwischen den einzelnen Stufen. Manche "mehrperiodische" oder "hierarchische" Modelle sind allerdings nicht spaltenweise, sondern zeilenweise gekoppelt. Auch solche Formen lassen sich algorithmisch erkennen. Nicht selten findet man nicht nur eine, sondern viele solcher Strukturen in Modellen.

In der Abschlussarbeit sollen Erkennungsalgorithmen aus der Literatur beschrieben und erweitert werden. Die Algorithmen werden in unserem Löser implementiert (und man kann direkt den Erfolg oder Misserfolg sehen). Bewertungen, welche Treppenstufenformen sich besonders gut für den Löser eignen sollen experimentell gefunden werden.

End-to-End Testing in GCG
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Wir entwickeln den quelloffenen Löser GCG für strukturierte ganzzahlige Programme (und wenn Sie dieses Thema bearbeiten möchten, sind Sie sehr wahrscheinlich schon damit in Berührung gekommen). GCG ist in C/C++ geschrieben und basiert auf dem SCIP Framework, für das es sehr ausgearbeitete illustrative Beispiel-Projekte gibt, die die Verwendung des Codes illustrieren. Im Rahmen dieser Arbeit sollen Beispiel-Projekte für Branch-and-Price mit GCG entwickelt werden. Diese Projekte dienen gleichzeitig dem End-to-end Testing einiger Komponenten des Lösers. Sie haben also sehr gute Kenntnisse in der Software-Entwicklung (u.a. in C/C++) und eine Vorstellung von End-to-End Testing. Wenn Sie diese Konzepte in der Praxis an GCG anwenden möchten, liegen Sie mit dieser Arbeit goldrichtig.

Erkennung von Strukturen in GAMS Modellen
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Wir entwickeln am Lehrstuhl den Löser GCG für strukturierte, ganzzahlige Programme. Dieser wendet auf ein eingelesenes Modell (in Form einer *.LP pder *.MPS Datei) eine Dantzig-Wolfe Reformuierung an und löst die Reformulierung dann mit Branch-and-Price. Wesentlicher Knackpunkt ist die "Erkennung" einer für die Reformulierung geeigneten Modellstruktur. In dieser Arbeit gehen wir davon aus, dass wir eine perfekte Ausgangslage haben, nämlich nicht nur ein *.LP File, sondern eine Modellierung in der Modellierungssprache GAMS. Sie müssen die aus GAMS kommende Information (das sogenannte Dictionary) auslesen, verabeiten und daraus eine für GCG verarbeitbare Information erzeugen. Der Prozess ist recht gut dokumentiert, erfordert aber noch einige eigene Gedanken nicht nur zur Architektur der Software, sondern auch zum bestmöglichen Ausnutzen der Modell-Struktur. Sie sollten sich sehr gut mit C/C++ auskennen und haben idealerweise schonmal mit SCIP gearbeitet. Machen Sie Ihre Arbeit gut, könnte als Resultat eine für jederfrau und jedermann benutzbare Schnittstelle zwischen GAMS und GCG entstehen.

Machine Learning in Decomposition Methods
Abschluss: M.Sc.
Kontakt: A. Helber
Details

Für viele kombinatorische Probleme können bessere Algorithmen entwickelt werden, wenn Wissen über die Problemstruktur genutzt wird, um das Problem in Teilprobleme zu zerlegen. Neuste Trends an der Schnittstelle von maschinellem Lernen und Operations Research zielen darauf ab, diese Algorithmen weiter zu beschleunigen, indem sie lernen, bessere heuristische Entscheidungen zu treffen. Ein anderes, weniger erforschtes und eher experimentelles Thema ist die Verwendung von gelernten Repräsentationen, um ganze Teilprobleme zu ersetzen.

Je nach Ihrem Interesse und Ihren Fähigkeiten sowie der Relevanz für unsere Forschung können wir das zu untersuchende Thema bestimmen.

Während reichlich Potenzial vorhanden ist, erfordern diese Themen sowohl einen sehr starken Hintergrund in der Theorie und Anwendung kombinatorischer Optimierungsmethoden (insbesondere Dekompositionsmethoden) als auch zumindest eine fortgeschrittene Erfahrung mit der Implementierung und dem Engineering von Machine Learning-Modellen. Kenntnisse in Python oder Julia sind erforderlich, in C/C++ hilfreich, da es interessant sein könnte, die Methoden in den Open-Source-Solvern SCIP oder GCG zu implementieren. Bei Interesse schildern sie bitte kurz ihre Vorkenntnisse sowie Themen und Methoden die sie interessieren und hängen sie ihren Notenspiegel an.

Master cutting planes in branch-and-price
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

In einem Branch-and-Price (B&P) Algorithmus lassen sich Cutting Planes in den Original- und in den Mastervariablen formulieren. Letzteres ist prinzipiell stärker und zum Beispiel in unserem Kurs "Column Generation and Branch-and-Price" oder diesem Artikel beschrieben.  In unserem Löser GCG sind solche Cuts rudimentär implementiert, aber wenig getestet oder verallgemeinert. Manche Cuts (wie Gomory oder Clique Cuts) sind noch nicht allgemein implementiert, obwohl die Theorie dafür da ist bzw. nur wenig erweitert werden muss.

In dieser Abschlussarbeit soll die Theorie der Cutting Planes in B&P aufgearbeitet und in GCG implementiert werden. Experimente auf allgemeinen (am Lehrstuhl verfügbaren) Modellen sollen die Wirksamkeit oder Unwirksamkeit solcher Cuts evaluieren.

 

MIP Presolve that preserves decomposition structure
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

Dantzig-Wolfe Reformulierung (oder Benders Dekomposition) sind gängige Techniken, um stärkere Relaxationen eines MIPs zu erhalten. Wir entwickeln den quelloffenen Löser GCG für strukturierte ganzzahlige Programme, der diese Techniken automatisch anwendet. Dazu muss er Strukturen in der Koeffizientenmatrix des MIPs "entdecken", die die Reformulierung erlauben.

MIP Presolve umfasst Techniken, ein MIP vor dem eigentlichen Lösen zu vereinfachen und zu verstärken, redundante Information zu entfernen, Ungleichungen zu verschärfen, Wertebereiche der Variablen einzuschränekn, usw. Oft wird ein MIP überhaupt erst durch diese Techniken in akzeptabler Zeit lösbar. Allerdings können die am Modell vorgenommenen (äquivalenten) Umformungen die Modellstruktur "zerstören" oder zumindest "verschleiern", was die Erkennung in GCG schwieriger oder unmöglich macht, manchmal dagegen aber auch überhaupt erst erlaubt.

In dieser Arbeit sollen gängige Presolve Techniken auf ihre Auswirkungen auf Modell-Struktur und ihre Erkennbarkeit theoretisch und experimentell untersucht werden.

 

strIPlib, a library of structured integer programs
Abschluss: B.Sc. oder M.Sc.
Kontakt: M. Lübbecke
Details

Unter anderem zum Testen unserer Dekompositionsalgorithmen für ganzzahlige Programme haben wir am Lehrstuhl eine Bibliothek von über 20000 strukturierten ganzzahligen Programmen (striplib.or.rwth-aachen.de). Diese Sammlung soll der wissenschaftlichen Community nützlicher verfügbar gemacht werden als in einem Verzeichnisbaum.

Wir haben zu den einzelnen Instanzen sehr viele Metadaten, nach denen man etwa filtern kann, um sich eigene, speziell zugeschnittene Testsets zusammenzustellen. Statistiken, auch als Grafiken, werden durch Skripte erzeugt und sollten dynamisch in die Webseite eingebunden werden. Die Interaktion mit unserem Löser GCG kann einen Mehrwert bieten, um direkt Eigenschaften von ggf. selbst hochgeladenen Modellen auswerten zu können.

Diese Abschlussarbeit verbindet das Wissen um die Struktur von ganzzahligen Programmen und (zumindest grundlegend) das Wissen um die Algorithmik von Branch-and-Price mit der Darstellungskraft der (Frontend und Backend) Webentwicklung, um einen wissenschaftlichen Nutzen zu schaffen.

Ausgewählte abgeschlossene Arbeiten

 

2023
Implementation, Evaluation and Extension of a Model for the Optimization of Grid-Related Measures in the Operation of Electrical Transmission Grids
Student/in: Lukas Ochse
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2023
Erstes Gutachten:
Zusammenfassung

Power transmission grids face increasing stress due to changes in power production and consumption patterns. The shift towards renewable, usually less steady energy sources or the deployment of "smart" devices have their contribution to this process. Currently, not all degrees of freedom in the power grid operation are exhausted; thus, the operation is sub-optimal concerning congestion and costs. While the power dispatch is optimized, this is not the case for topology measures, mainly due to computational burdens. This thesis analyzes the issue of using topology measure optimization integrated into an optimal power flow problem, the so-called Security Constrained DC Optimal Transmission Switching (SC-DC-OTS) problem. An integrated problem formulation of a Power Transfer Distribution Factor (PTDF) based SC-DC-OTS is provided together with its implementation. Further, an offline algorithm is proposed to find topology measure candidates efficiently, thereby reducing the solution space of the SC-DC-OTS model, the so called Power Set Poisoning Depth-First Search (PSPDFS) algorithm. In parallel, the implementation explores improvements to the ergonomics of modeling tasks. Four simulation studies are conducted to evaluate the functioning and performance of the model implementation, as well as the potential of the PSPDFS algorithm. Considering topology measures and security constraints leads to a vast amount of side conditions in the model, and thus, considering all potential topology measures is not manageable. The simulations show that in some cases, PSPDFS can considerably reduce the number of topology measures.

Mixed Integer Linear Programming Methods to Generate Attacks on Binarized Neural Networks and to Increase their Robustness
Student/in: Hendrik Höfert
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2023
Erstes Gutachten:
Zusammenfassung

Binarized Neural Networks (BNNs) are feed-forward neural networks with fully connected layers that purely use binary weights. The evaluation is highly efficient, which makes it attractive to use them in low-power settings since their performance is close to the performance of linear neural networks. However, robust networks are important, especially in settings that are safety-critical. So-called attacks on neural networks are small perturbation vectors that are added to the input that lead to different (pre-defined) results. Existing methods to generate attacks mostly use gradient-based methods, but the binary, non-differentiable nature of the BNNs renders gradient-based methods impossible. One more recent approach already makes use of mixed integer linear programming (MILP) models. In this body of work, we reproduce the results of existing approaches that make use of MILP models. We come up with new formulations and we show that they are stronger performance- and results-wise. Furthermore, we show that a reformulation of these models into a column generation approach does not seem to be practical and demonstrate an MILP model to alter the network to be robust against the previously generated attacks.

2022
A Price-and-Branch Heuristic for Line-Haul Network Optimization
Student/in: Miléna Tyra
Studium: Wirtschaftsingenieurwesen (WPT) |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

This work explores if scheduled service network design programs can effectively support the Deutsche Post DHL Group (DP-DHL) in the tactical planning of their service networks. The DP-DHL operates service networks using trucks to transport packages between regional terminals. For cost-efficient transportation, packages are consolidated at hubs, which requires close coordination of the operated services. The underlying combinatorial optimization problem is known as the scheduled service network design (SSND) problem. SSND programs can decide which services to operate and how to transport commodities based on these services to minimize the total operational costs. In the case of DP-DHL, a variety of real-world constraints and operational options need to be considered during the program development. The proposed SSND program is solved by a price-and-branch heuristic, where services and paths for commodity flows are generated based on time-space graphs in column generation schemes. The program simplifies the DP-DHL problem to apply SSND programs known from literature to the DP-DHL case. Within the simplified framework, the currently operated service network under consideration could be optimized in terms of costs. The linear programming relaxation solution values show significant optimization potential, which could be partially translated into mixed-integer solutions. It can be challenging to fully model the real-world complexity and to design large and robust service networks with SSND programs. However, the improvements achieved indicate that SSND programs could be used as part of advanced solution procedures that can overcome modeling and runtime challenges.

Algorithmische Struktur Erkennung in mixed-integer Programmen für Dantzig-Wolfe Reformulierung
Student/in: Julian Rehm
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Die Vorteile der Danzig-Wolfe-Reformulierung (DWR) beim Lösen von gemischt-ganzzahligen Programmen (MIPs) sind gut dokumentiert. Damit DWR gute Ergebnisse erzielt, muss jedoch eine bestimmte Struktur in der Nebenbedingungsmatrix des MIPs vorhanden sein. In den meisten heutigen Solvern muss der Benutzer solche Strukturen für den Solver bereitstellen. Es gibt in der Literatur einige Vorschläge zur Automatisierung der Strukturerkennung, von denen jedoch einer eine sehr wünschenswerte Prämisse hat, da er keine Benutzereingaben erfordert, d.h. keine Kenntnisse über die Problemstruktur voraussetzt. Der in der Arbeit "Structure detection in mixed-integer programs" von Khaniyev et al. vorgeschlagene Algorithmus erkennt eine bordered block diagonal (BBD) Struktur. Er schlägt eine Metrik für die Güte solcher BBD-Strukturen vor und implementiert einen greedy, auf community detection basierenden Ansatz. Diesen Algorithmus haben wir im GCG Solver implementiert, so dass wir die wichtigsten Designentscheidungen nachvollziehen sowie die Performance testen konnten.

Algorithms to detect maximum embedded reflected network sub matrices in linear programs
Student/in: Jordan Rosenstein
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Extracting special structures from coefficient matrices is a known practice to solve linear programs more efficiently. One of these extraction problems is the detection of maximum embedded reflected network matrices (DMERN). That is finding a maximal sub matrix in our coefficient matrix such that by multiplying a number of its rows with −1 this sub matrix contains in each column at most one -1 entry and at most one +1 entry, while all other entries are zero. The goal of this bachelors thesis is to give an introduction into the DMERN problem and provide a collection and explanation of solution approaches that can be found in the literature.

An analysis of an extended image-based approach to detect structural similarity among mixed integer programs
Student/in: Jurgen Lentz
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

This thesis implements, documents and analyzes two different image-based approaches to detect structural similarity among mixed integer programs. The first approach detects structural similarity among mixed integer programs using the constraint coefficient matrix. Therefore, the constraint coefficient matrix is permuted using decomposition techniques of the Generic Column Generation solver (short GCG) and is visualized as an image. Several instances of strIPlib are used to create these images and then passed on to train a convolutional autoencoder. The trained convolutional autoencoder can compute feature vectors that represent latent structural features of the mixed integer program. Thereafter, the feature vectors are used to measure similarity among mixed integer programs. The aforementioned approach is extended by adding the left-hand and right-hand side vectors and the objective coefficient vector to the constraint coefficient matrix and thus creating more insightful images. These images are easily created using the developed visualization tool for decompositions in PyGCGOpt. This procedure generates our second approach to detect structural similarity among mixed integer programs. Finally, the analysis of both approaches shows that both approaches are equally well suited to detect structural similarity among mixed integer programs.

Artificial Neural Networks Enhanced Distribution System State Estimation
Student/in: Shekhar Dure
Studium: Data Analytics and Decision Science |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

State estimation is responsible for the stable and efficient operation of electric power system and plays a vital role in power system monitoring and control. The increasing shift towards use of renewable energy sources (RES) in electric power system has introduced bi-directional flow of power in the electric power system, one from the transmission system and other from the renewable energy resources which can violate the network operating constraints which can further lead to the network failure. Therefore, state estimation in distribution networks have become very critical. Distribution System State Estimation (DSSE) algorithms compute the state variables of an electrical network complex voltages (magnitude and phase angle) using input measurements of electric bus active and reactive power injections, branch power flows and bus voltages magnitudes taken from the system. The main challenge for implementation of state estimation in distribution network is the limited number of measurements. System is generally unobservable (partially observable), therefore an attempt to solve this problem of lacking real time measurements is the employment of so-called pseudo-measurements to ensure the observability of the system and a reliable estimation. Therefore, the validity of state estimation depends on the accuracy of generated pseudo-measurements. The focal point of this thesis is to device an alternative approach to generate and model pseudo-measurement in reference to distribution system state estimation. In the proposed approach, Artificial neural networks (ANNs) are used to generate pseudo-measurements where few real measurements are used in conjunction with typical load and generation profiles. The error between the load and generation profiles (target output of ANN) and ANN output is modeled through Gaussian Mixture Model (GMM). The state estimation of three different networks are computed using the pseudo-measurements generated using the proposed methodology and compared with the actual state estimation values to validate the quality of state estimation results using the predicted pseudo-measurements. We have also demonstrated our proposed approach of pseudo-measurement modeling for state estimation on network with topological changes.

Can learning-based approaches optimize optimization? A case study on energy grids
Student/in: Kevin Kruse
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten: W. Unger
| Zweites Gutachten: M. Lübbecke
Zusammenfassung

Energy grids are the backbone of every developed country. Currently, the grid topology is considered to be fixed. Topological changes are mostly executed in case of overloads or violations of safety margins. Thus, primary measures to control the power grid are market-based ones, like actively steering power plants. Recent research also identified the potential of optimizing the power flow including topological measures, like transmission element switching. The mathematical complexity of this formulation prohibits its practical usage. Currently, results are either obtained too slowly or violate critical security requirements using heavily simplified models. This work presents implementations of the traditional problem formulation and their restrictions. Alternative solution methods like nearest neighbor and reinforcement learning are implemented and compared against traditional optimization methods.

Combinatorial Attacks on Binarized Neural Networks
Student/in: Jérôme Lenßen
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

In this work, we explore combinatorial attacks on (binarized) neural networks. The "attacks" are small changes to the input data, such that the network misclassifies the input. To construct such combinatorial attacks, mixed-integer programs are used, instead of the gradient of the network, which is usually used. In the first part of the thesis, we reproduce the Iprop attack proposed by Gupta et al. in "Combinatorial Attacks on Binarized Neural Networks". Binarized neural networks are hereby aritficial neural networks with weights restricted to 0 and 1. We compare our results with those reported in the paper and analyze challenges in the implementation of the proposed method. In the second part, we extend the attacks to continuous neural networks and compare LP-based attacks with gradient-based attacks. We answer the question in which scenarios the LP-based approaches offer better performance and evaluate the strength of our formulation. Furthermore, we analyze whether successful "attacks" can be transferred to other network architectures and if LP-based attacks generalize better than gradient-based attacks.

Creating Train Timetables with Associated Scheduled Passenger Routings Based on Integer Linear Programming
Student/in: Johannes Salentin
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

In the course of planning railway transportation systems multiple problems have to be solved. Typically, those problems are solved sequentially in different stages, but since the planning stages are highly dependent on each other, it is beneficial to follow a more integrated approach. Inspired by the problem statement of the informatiCup 2022 "Abfahrt!", the integrated problem of creating a feasible train timetable with an associated scheduled passenger routing that minimizes the overall delay of all passengers will be investigated. This means, we direct trains and passengers individually through a public transportation network (PTN), while respecting all capacity constraints at all times. This problem turns out to be strongly NP-hard.  We propose different solution approaches based on integer linear programming and implement them to analyze their performance on examples. As a result, the approach based on a space-time graph representing actions on the original PTN outperforms the other presented concepts.

Impact of LP-Constraints Classification on the Strength of Dantzig-Wolfe Reformulation Dual Bounds
Student/in: Dawid Jażewicz
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Diese Arbeit untersucht das Verhalten von Dantzig-Wolfe Dekompositionen mit Hinblick auf die Klassifizierung von Restriktionen. Anstatt für die Untersuchung alle möglichen Teilmengen der Restriktionen als Dekomposition zu betrachten, erlaubt das Klassifizieren eine Möglichkeit deutlich weniger Dekompositionen zu betrachten. Somit sind Analysen auf größeren Instanzen möglich. Es wird geprüft, ob man anhand einer Zuordnung der Restriktionen in Klassen eine Regel für das Verhalten der dualen Schranken ableiten kann. Zudem wird analysiert, welchen Einfluss die Klassen auf das Lösen der einzelnen Dekompositionen haben, insbesondere auf die Lösungsdauer.

Improving the Cash Flow of the Company by Prescribing the Collections Manager's Actions through an Artificial Intelligence Based Predictive Worklist
Student/in: Premnath Eswaran
Studium: Data Analytics and Decision Science |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Collection and Dispute Management, a part of the broader Order to Cash process, is responsible for collecting the credit back from the customer and improving the cash flow. Bayer's collections process suffers a severe overdue problem, owing to delayed payment by the customers. The current reactive nature of the collection process poses a significant challenge for reducing the average delinquent days. Hence a proactive collection strategy with a specific collection action for each customer is the need of the hour. This thesis focuses on understanding the business problem and providing an analytical solution for the collection team of one of the country. The solution employs Machine Learning via two modules: Invoice prediction and Days to Pay prediction. Finally, the Predictive Worklist module is the decision model that ensembles the results from the other two modules and the behavioral characteristics of the customer to create a recommended action for each customer. A detailed analysis of the problem and performance of those modules are evaluated. The proposed model serves as base for further extension of the project for other countries.

Intelligent selection of the hyperparameters & topology of neural networks for the determination of a measurement model
Student/in: Muqi Liu
Studium: Wirtschaftsingenieurwesen (EET) |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

The accurate determination of the measurement uncertainty is important in the production environment to avoid economic losses due to erroneous decisions caused by measurement errors. Prerequisite for determining the measurement uncertainty is the description of the measurement process with the help of a model. Artificial neural networks (ANN) have the potential to create a model that validly describes the measurement process. However, there are no guidelines for the selection of the hyperparameters and topology of the ANN that are used in this context. In this master’s thesis, a method for optimized hyperparameter and topology selection for model building in measurement uncertainty determination using ANN was developed. The optimization of the hyperparameters and topology of ANN was first formally described as a mathematical optimization problem. To solve the problem, different algorithms (including classical algorithms, genetic algorithms) were identified and adapted for the problem of modeling in the determination of measurement uncertainty. Finally, the methods were evaluated using several measurement data sets.

Mixed integer Program for Covering Rectilinear Polygons
Student/in: Daniel Sous
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

In this Master Thesis, we investigate Mixed Integer Programs (MIPs) for optimally solving the problem of covering rectilinear polygons with a minimum number of axis parallel rectangles. Since larger instances involve millions of possible rectangles inducing long solving times, it might be necessary to choose a MIP formulation that can be solved with column generation. This allows us to start with a basic feasible solution and dynamically add new rectangles improving the current solution. In general, solutions to this NP-hard problem find applications in the fabrication of DNA chip arrays, in VLSI design, and image compression. In particular, aiming at image compression, other shapes like ellipses will be tested to improve the compression rate. Additionally, we investigate an approach that allows the model to select the shapes on its own to achieve even higher compression rates. Furthermore, the MIPs can be extended to allow for a lossy image compression. This thesis will elaborate and implement the introduced approaches to test them for their computational feasibility.

Practical Approaches to Nesting Different Classes of Shapes
Student/in: Janos Pidubnij
Studium: Data Science |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

The nesting problem belongs to the class of cutting and packing problems. A two-dimensional cutting problem is called a nesting problem when the two-dimensional objects that need to be cut are non-rectangular. The objective is usually to minimize waste by utilizing the available material in the most efficient manner. Nesting problems are often encountered in manufacturing industries such as wood, steel, and textile industry. The geometric properties of irregularly shaped objects make solving nesting problems in practice very challenging. In this thesis, we cover the existing approaches to solving nesting problems as well as the geometric tools utilized by these approaches. Additionally, we explore a methodology combining two different strategies, namely, a heuristic algorithm and a mixed-integer programming model.

Reduced Cost Variable Fixing in Branch-Price-and-Cut Algorithms
Student/in: Alexander Helber
Studium: Wirtschaftsingenieurwesen (EET) |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Reduced cost variable fixing is a classic technique for reducing the problem size when solving mixed-integer program. It allows fixing variables whose reduced costs are higher than the absolute gap. Reformulating problems with Dantzig-Wolfe decomposition and solving them with branch-price-and-cut algorithms often leads to tight dual bounds and smaller absolute gaps, but application of RCVF is not straightforward in these algorithms. Fixing the variables in the reformulation is not very promising but fixing variables of the original problem is not immediately possible, as no reduced costs are known for them. This thesis explores various ways to compute reduced costs of original variables and therefore apply RCVF in BP&C both from a theoretical and computational perspective.

Relaxationen für ganzzahlige lineare Programme
Student/in: Stefan Rogosinski
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

In dieser Arbeit untersuchen wir verschiedene Relaxationen für ganzzahlige lineare Programme und betrachten dabei insbesondere deren Anwendung auf das Stable Set Problem. Wir analysieren Dantzig-Wolfe- Reformulierungen, die Corner-Relaxation und deren Variationen, die Sherali-Adams-Relaxation und die Lovasz-Schrijver-Relaxation anhand folgender Gesichtspunkte: Wie genau ist die Relaxation? Kann man die konvexe Hülle bestimmen? Wie hoch ist der Zeitaufwand? Wie hängen diese Faktoren möglicherweise von der Struktur des Graphen ab? Kann man das Problem auf ein Teilproblem reduzieren? Kann man verschiedene Verfahren kombinieren? Kann man die Verfahren auch auf andere Probleme anwenden?

Sentiment Analysis using Natural Language Processing on (Text, Social Media and Application Reviews)
Student/in: Saurabh Potdukhe
Studium: Data Analytics and Decision Science |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Texts written in natural language are an unstructured data source that is hard for machines to understand. The amount of text in the world wide web is growing every minute. To deal with this huge number of unstructured data automated text analysis is crucial. Natural Language Processing (NLP) is part of artificial intelligence that makes natural language texts comprehensible for machines. Natural language processing (NLP) techniques can contribute to this problem by offering automated means to do preprocessing, text classification, feature extraction, and topic modelling. Social networks, like Facebook or Twitter, Application like Amazon or eBay are a phenomenon that has recently transformed numerous aspects of our lives. The impact of these platforms is no longer limited to entertainment or personal presentation of individuals. Indeed, they have formed a new sheer of business, with some emerging companies focusing primarily on this platform and others, more traditional ones, expanding their marketing efforts there. My intense research is being performed in order to efficiently categorize, filter, detect text and reviews on the customer-generated content on social networks and application reviews. One of the key segments of this effort is sentiment analysis and goal is to create different models on sentiment of the posts, comments, reviews or other forms of reactions users generate in relation to a company or a product. On the basis of that checking computational performance and results.

Über die Evaluation und Optimierung von konvergenten und divergenten Produktionsstrukturen
Student/in: Max Korfmacher
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Um die Frage zu beantworteten, ob sich die Investition in ein bestehendes Produktionssystem lohnt, muss man beide Konfigurationen anhand von Kenngrößen miteinander vergleichen. Dazu wird die Produktionsstruktur als Maschinen, welche über Puffer miteinander verkettetet sind, abstrahiert. Dabei fangen die Puffer Maschinenausfälle ab, damit nicht weitere Arbeitsschritte auf Grund von Materialmangel oder mangelnder Kapazität im Output stillstehen. Ein Puffer kann zum Beispiel ein Förderband sein, auf dem sich Zwischenprodukte aufstauen können. Desweitern soll das Modell auch konvergente und divergente Produktionsströme abbilden, das heißt Maschinen können mit mehr als zwei Maschinen verbunden sein und somit zum Beispiel eine Endmontage beschreiben. Zur Bewertung verschiedener Konfigurationen kann man die Ausbringung als Kenngröße verwenden, welche die Produktionsmenge bezüglich einer Zeiteinheit beschreibt. Zudem ist der Wirkungsgrad, also die Ausbringung im Vergleich zur kleinsten Produktionsrate einer Maschine, interessant. Zur Messung dieser Werte in der Realität, müsste allerdings die Produktionsstruktur umgebaut werden, was mit erheblichen Kosten verbunden. Somit muss auf eine Simulation oder ein numerisches Verfahren zurückgriffen werden. In dieser Arbeit werden Algorithmen, zur Bewertung von konvergenten und divergenten Produktionsstrukturen aus der Literatur erläutert. Der Input ist ein Netzwerk aus Maschinen, wobei diese durch Kennzahlen zur Produktionsrate, Ausfallzeiten und Reparaturdauer beschrieben werden und die Puffer über ihre Kapazität definiert sind. Des Weiteren wird der Fokus auf der Anwendung dieser Algorithmen in der Praxis liegen, insbesondere im Vergleich zur Simulation. Dazu wird ein Algorithmus prototypisch umgesetzt. Zu Beginn der Arbeit werden die Ansätze der verschiedenen Algorithmen aus der Literatur erläutert. Im Anschluss wird die Vorgehensweise der Algorithmen erklärt, dabei wird der mathematische Hintergrund beleuchtet. Der letzte Abschnitt beschäftigt sich mit der Güte der Bewertung des implementierten Algorithmus und mit seiner Laufzeit.

Unterstützung der Suche: Wie Maschinelles-Lernen-Methoden helfen, traditionelle kombinatorische Optimierungsprobleme zu lösen, eine Überprüfung und Implementierung
Student/in: Jonathan Alegria
Studium: Data Analytics and Decision Science |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Recent times have seen the rise of a research current which aims to solve classical Combinatorial Optimization (CO) problems through the help of Machine Learning (ML), and specifically in this work Deep Reinforcement Learning (RL) methods. One of the problems where these two exciting fields meet one another tackles the question of how to guide the branching process within a Branch and Bound algorithm, where sequential decisions must be done in order to reach an optimal solution. To this extent, the goal  of the current work is to gain insight of the state of the art methodologies dealing with such a problem, and through an implementation and an experimental study, to provide an comprehensive view of the impact of employing RL to aid the solving of CO problems.

Varianten des Temporal Facility Location Problems: Komplexität, Modellierung und Anwendung auf die Standortwahl von Ladestationen für Elektrofahrzeuge
Student/in: Anne Schönhofen
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2022
Erstes Gutachten:
Zusammenfassung

Aktuell sind Klimaschutzmaßnahmen in vielen Sektoren von großem gesellschaftlichem und politischem Interesse, um den anthropogenen Treibhauseffekt einzudämmen. Der Verkehrssektor nimmt dabei eine entscheidende Rolle ein, da dieser zu den weltweit größten Verursachern von Treibhausgasen zählt. Im Rahmen der Mobilitätswende wird angestrebt, in den kommenden Jahren die bisher überwiegend verbreiteten Verbrennungsmotoren durch Fahrzeuge mit hybridem oder vollelektrischem Antrieb weitestgehend zu ersetzen. Damit einher geht der Ausbau der nötigen Ladeinfrastruktur und Entscheidungen bezüglich der Standortwahl und Größe von Ladestationen. In dieser Masterarbeit wird das Problem basierend auf dem Temporal Facility Location Problem mit Methoden der diskreten Optimierung mathematisch modelliert. Dieses stellt eine zeitliche Erweiterung des klassischen Standortproblems dar, in der Kunden jeweils nur für ein gegebenes Zeitintervall an einen Standort angebunden werden. Die neue Restriktion lautet, dass zu keinem Zeitpunkt mögliche Kapazitäten der Standorte überschritten werden dürfen. In einer detaillierten theoretischen Analyse werden zunächst verschiedene Varianten des grundlegenden deterministischen Temporal Facility Location Problems untersucht. Neben einer jeweiligen Komplexitätsanalyse werden beispielsweise Untersuchungen bezüglich der Approximierbarkeit durchgeführt sowie verschiedene mathematische Formulierungen hergeleitet und verglichen. Daraufhin werden die Probleme in ihren Online-Varianten untersucht und Resultate bezüglich der Kompetitivität vorgestellt. Anschließend werden realitätsnahe Charakteristika des Anwendungsbereichs in die Problemdefinition integriert, indem verschiedene Modifizierungen vorgenommen werden, und erneut eine detaillierte theoretische Analyse durchgeführt.

2021
A Data-Driven Approach to Reduce the Size of Integer Programming Test Sets while Maintaining their Diversity
Student/in: Tim Donkiewicz
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Schneider
Zusammenfassung

The use of machine learning methods such as artificial neural networks or clustering algorithms is becoming more and more popular in the optimization community. Connecting to this trend, we propose a method that, instead of tuning mixed-integer programming solvers' behavior, facilitates testing (modified) solver behavior. Utilizing dynamic clusterings and solving mixed-integer programs, we select and visualize different diverse subsets of the test data available in the structured integer programming library strIPlib that are just as representative but exhibit a much smaller size. The generated subsets do not only comprise a strIPlib collection and a 'general-purpose' benchmark test set, but also a method to generate completely customized, diverse experiment test sets, tailored to the experiment that is to be executed with them.

A Scripting Interface for a Generic Branch-Cut-and-Price-Solver
Student/in: Steffan Schlein
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Mixed-integer programming (MIP) is a common technique to model optimization problems. They can be solved with the decomposition approach of Dantzig-Wolfe reformulation (DWR) and the branch-cut-and-price (BC&P) algorithm. Many state-of-the-art software packages for solving MIPs provide scripting interfaces to interactively model and optimize these problems. We introduce PyGCGOpt, a Python interface for the generic BC&P solver GCG. The interface allows to model MIPs, to construct and visualize decompositions, and to implement solvers for pricing problems which occur from DWR. We provide example applications of our interface and show that it interacts with the solver without a significant decline in performance.

Anwendung quantitativer Methoden zur Lieferterminermittlung neu eingehender Aufträge in einer der Praxis entlehnten Job-Shop-Scheduling-Problemstellung
Student/in: Lukas Nadenau
Studium: Wirtschaftsingenieurwesen FR Bauingenieurwesen |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Das klassische Job-Shop-Scheduling-Problem besteht darin, eine optimale Zuordnung anfallender Aufgaben zu bestehenden Maschinen zu finden. Die Optimalität der Lösung kann unterschiedlich definiert sein, zielt in den meisten Fällen aber auf eine möglichst schnelle und/oder kostengünstige Abwicklung ab. Die vorliegende Arbeit erweitert dieses klassische Modell gemäß einer der Praxis entlehnten Problemstellung um eine dynamische Komponente. In eine schon bestehende Lösung sollen nun neu hinzukommende Aufgaben integriert werden. Die neu entstandene Situation wird separat modelliert und hinsichtlich eines eigenen Optimalitätskriteriums betrachtet.

Automatische Dantzig-Wolfe-Zerlegung in Julia
Student/in: David Meichel
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Dantzig-Wolfe Zerlegung ist eine bekannte Methode, mit der lineare gemischt-ganzzahlige Progamme (engl. mixed integer programs), die eine gewisse Struktur haben, umformuliert und so bessere Grenzen für den optimalen Zielfunktionswert erhalten werden können. Die Dantzig-Wolfe Zerlegung wird daher in Branch-and-Bound eingesetzt, wo die Laufzeit von der Qualität der ermittelten Grenzwerte abhängt. JuMP ist eine Modellierungsprache für mathematische Optimierungsprobleme, die in der Programmiersprache Julia eingebettet ist; Coluna ist ein Framework, das JuMP erweitert und die Anwendung einer Dantzig-Wolfe Zerlegung ermöglicht. In Coluna muss jedoch der Benutzer die Problemstruktur beschreiben, welche die Anwendung einer Dantzig-Wolfe Zerlegung ermöglicht. Wir beschreiben, wie dem Benutzer diese Aufgabe abgenommen werden kann und präsentieren unsere Implementierung einer automatischen Dantzig-Wolfe Zerlegung für Coluna. Die Automatisierung der Dantzig-Wolfe Zerlegung erfolt in zwei Schritten. Zunächst erklären wir, wie eine Menge von potentiellen Strukturen für ein gegebenes lineares gemischt-ganzzahliges Programm mithilfe der Indexmengen der Bedingungen identifiziert werden kann. Im zweiten Schritt präsentieren wir verschiedene Scores aus der Literatur, welche zum Ziel haben, die für eine Dantzig-Wolfe Zerlegung potentiell beste Struktur in einer Menge von Kandidaten zu identifizieren.

Classification of MIPs for Dantzig-Wolfe reformulations A graph-based analysis of underlying problem specific structure in mixed integer programms
Student/in: Paul Alexander Raffelsiefen
Studium: Wirtschaftsingenieurwesen |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

The selection of the optimal decomposition for Danzig-Wolfe reformulations presents a difficult task for a generic MIP solver. The determination of the structure of the program can contain valuable information for this process. Therefore detection algorithms are used to extract the characteristics of the MIP. In this thesis a new approach is introduced to classify the MIP as a whole, in contrast to commonly used constrain and variable classification. A graph is used to summarize and analyse the extracted features of the MIP. This graph is generalised, by estimating the sets of indices, that were used for the creation of the MIP. Afterwards can the compression with other graphs, which represent different types of MIPs, result in a categorization of the examined MIP. The implementation of this approach showed promising success, when tested with multiple different types of MIPs. For well structured MIPs, the algorithm was able to reliable detect the type of the MIPs and recommend decompositions accordingly. Problems exist in the handling of small irregularities in the MIPs or structure changed by the presolving process. Therefore, further improvements of the robustness of the algorithm could enhance the classification quality.

Deep Learning for Visual Speech Recognition in Medical Applications
Student/in: Roney Mathew
Studium: Data Analytics and Decision Science |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Visual Speech Recognition, also called lipreading, is the task of interpreting speech and predicting text by only analyzing the movements of a speaker’s mouth. Lipreading is a difficult task for both humans and computers. The field of Machine Learn and its promising sub-field Deep Learn, have proven to be successful in tackling complex problems. Recent advancements have enabled lipreading systems to use deep learn models which are trained end-to-end. This thesis describes the development of such a deep learn based lipreading system which as an end goal will aid temporarily speech impaired patients in the intensive care units of hospitals in communicating more efficiently. It approaches the problem by breaking it down into two stages which are trained separately. The first stage predicts audio features from video frames and the second stage takes the predicted audio features and predicts the spoken text. The audio data that is available can be utilized for training the system. The lipreading system that was developed using this approach was able to achieve results close to the popular baseline model LipNet. Further, the collective behavior of the two stages of the model was evaluated. The presented insights serve as valuable input for future research in the broader project to which this thesis belongs.

Effizientes Lösen von Flowbased-Strommarktmodellen
Student/in: Georg Wicke-Arndt
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Aufgrund der Energiewende ist es unabdingbar, dass sich der europäische Strommarkt in den nächsten Jahren deutlich verändern wird. Um diese Veränderungen vorherzusagen und darauf zu reagieren, wird das europäische Stromnetz mittels linearer Programmierung simuliert. Diese Arbeit ist in Kooperation mit der Firma Consentec GmbH entstanden, wo entsprechende Simulationen durchgeführt werden. Der Anspruch an die Genauigkeit der Simulation ist dabei in den letzten Jahren gewachsen. Konkret sollen Stromflüsse nicht mehr alleine auf der Ebene einzelner Länder oder Zonen (NTC), sondern auf Leitungsebene (flow-based) abgebildet werden. Dabei entstehen sehr viele Nebenbedingungen, von denen jedoch die allermeisten den Lösungsraum nicht verändern. Es werden verschiedene Ideen diskutiert, wie mit diesen Nebenbedingungen umgegangen werden kann. Vor allem wird ein Ansatz präsentiert, der das Herausfiltern der relevanten Nebenbedingungen deutlich beschleunigt.

Hierarchical Strong Branching and Other Strong Branching-Based Branching Candidate Selection Heuristics in Branch-and-Price
Student/in: Oliver Gaul
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Schneider
Zusammenfassung

Für gemischt-ganzzahlige Programme hat die Wahl der richtigen Branching-Variable einen großen Einfluss auf die Größe des resultierenden Branch-and-Bound (B&B) Baums, und damit auch auf die Laufzeit des gesamten Algorithmus. Vollständiges starkes Branching, also die Auswahl von Variablen durch vollständige Auswertung der Kindknoten die für die entsprechenden Kandidaten entstehen würden, ist gut darin, Bäume klein zu halten, wird aber wegen des hohen Berechnungsaufwand im Verhältnis zur eingesparten Baumgröße normalerweise nicht in B&B verwendet. Stattdessen wird es mit anderen Heuristiken kombiniert, was zu einigen der erfolgreichsten Kandidatenauswahlheuristiken für allgemeine Problem führt, wie zum Beispiel hybrides Pseudokosten/starkes Branching oder Zuverlässigkeitsbranching. Da die Auswertung einzelner Knoten in Branch-and-Price (B&P) wegen der durchzuführenden Spaltengenerierung im Allgemeinen länger dauert als in B&B sind sowohl die Kosten von starkem Branching als auch die Vorteile davon, einen kleinen Baum zu erhalten in B&P erhöht. Dies ändert potentiell die relative Leistung von bestehenden Auswahlheuristiken, und gibt die Möglichkeit, neue Heuristiken zu erstellen. Eine dieser neuen Heuristiken, genannt hierarchisches starkes Branching, kombiniert andere Heuristiken mit starkem Branching in einer hierarchischen Art und Weise. Wir erweitern hierarchisches starkes Branching, unter anderem indem wir es mit hybridem Pseuodokosten/starkem Branching und Zuverlässigkeitsbranching kombinieren. Danach evaluieren und vergleichen wir die Effektivität verschiedener, teilweise starkes Branching-basierten Kandidatenauswahlheuristiken, sowohl für Branching auf Originalvariablen als auch für Ryan-Foster Branching.

Mathematically optimized demand side management for the production of perishable goods
Student/in: Lovis Heinrich
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Die Modellierung eines Produktionsprozesses als gemischt ganzzahliges lineares Programm (MILP) erlaubt es, variable Kosten durch das Ausnutzen niedriger Strompreise zu sparen. Verkomplizierende Aspekte wie verderbliche Materialien können die Rechendauer solcher Optimierungsprobleme erheblich erhöhen. Dies führt oft zu ungenutztem Potenzial in der Lösungsqualität, weswegen effizientere Lösungsverfahren benötigt werden. Bei einer periodischen Produktionsplanung wird dasselbe MILP immer wieder gelöst, wobei sich nur die Eingangsdaten ändern. Allerdings wird die Erfahrung über Muster im Lösungsprozess meist nicht genutzt. In dieser Arbeit wird ein Produktionsplanungsproblem mit verderblichen Zwischenprodukten betrachtet. Es wird mit Hilfe von lazy constraints modelliert, d.h. verkomplizierende Ungleichungen werden separiert und während des Lösungsprozesses on-the-fly hinzugefügt. Anschließend wird gezeigt, dass ein neuronales Netz verletzte lazy constraints mit hoher Präzision vorhersagen kann, indem es Erfahrungen aus zuvor gelösten Instanzen nutzt. Das neue Modell ist bis zu 34% schneller als das schnellste konventionelle Modell und die lazy-Methode.

Optimal Operation of Laser Powder Bed Fusion Machines
Student/in: Luca van der Peet
Studium: Computational Engineering Science |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Eine Laser Powder Bed Fusion (LPBF) Maschine erstellt 3D Objekte durch schichtweises Aufschmelzen von Metallpuder mit Lasern. Bei diesem Prozess bieten sich mehrere Aspekte zur Optimierung an. Einerseits ist das Finden der optimalen Anzahl und Ausrichtung der Scanner für eine gegebenes Arbeitsstück von Belang. Außerdem bedarf es des bestmöglichen Pfades des Prozesskopfes über die Arbeitsfläche und letztlich muss die Arbeitslast auf die Scanner im Prozesskopf aufgeteilt werden. Diese Probleme werden als Mixed-Integer Programs modelliert und mit dem Gurobi Löser berechnet.

Optimization of a bank portfolio regarding the net interest income in consideration of regulatory metrics by means of mathematical programming
Student/in: Hanna Heinemann
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Die Masterarbeit befasst sich mit einem klassischen Optimierungsproblem aus der Finanzwelt, der für Banken spannenden Fragestellung der Portfolio-Optimierung. Es wird das Spannungsfeld betrachtet, dass Banken unter anderem die Maximierung ihres Zinsergebnisses anstreben, jedoch auch dazu verpflichtet sind gewisse regulatorische Vorgaben einzuhalten. Im Fokus dieser Arbeit standen einerseits das Aufsetzen einer fachlichen Konzeption des Optimierungsmodells sowie die technische Realisierung der für die Optimierung zusätzlich erarbeiteten Vorverarbeitungen. Andererseits schließt die Arbeit das Aufstellen sowie das entsprechende Umsetzen eines mathematischen Modells basierend auf ausgewählten regulatorischen Metriken ein. Es wurde ein lineares Optimierungsmodell aufgestellt, welches die Metriken NII (Net Interest Income), EVE (Economic Value of Equity) und NSFR (Net Stable Funding Ratio) sowie die Kapitalquoten und die Bilanz umfasst. Die Arbeit wurde fachlich von einem Anbieter von Softwareprodukten im Finanzwesen begleitet und die Optimierung basierend auf den Ergebnisdaten aus deren Standard-Softwarelösung für das Meldewesen von Banken aufgesetzt.

Orthogonal Packing Problems
Student/in: Johannes Plett
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Die vorliegende Arbeit thematisiert die theoretische und praktische Analyse von gemischt ganzzahligen Programmen für orthogonale Verpackungsprobleme. Ziel der Arbeit ist es das Verpackungsproblem, welches in der Literatur als Multiple Bin Size Bin Packing Problem bekannt ist, zu untersuchen und Lösungsalgorithmen anzugeben. Insbesondere die Bedingung, dass Artikel überlappungsfrei in der Verpackung platziert werden müssen, hat in mehreren Dimensionen Probleme bereitet, wodurch Techniken aus dem eindimensionalem Fall nicht oder nur schwer erweitert werden können. Aus diesem Grund werden zunächst verschiedene Modellierungstechniken für das Einhalten dieser Bedingung an den Teilproblemen Orthogonales Packing - und Orthogonales Knapsack Problem vorgestellt und sowohl theoretisch als auch praktisch verglichen. Hierbei zeigt sich, dass kompakte Modelle, welche auf Relationen beruhen, die besten praktischen Ergebnisse liefern, obwohl andere Modellierungstechniken wie beispielsweise die Diskretisierung bessere theoretische Eigenschaften aufweisen. Die in der Praxis erfolgreichen Techniken werden daraufhin auf verschiedene Weisen für das Multiple Bin Size Bin Packing Problem erweitert und die Möglichkeiten diesbezüglich erneut in der Praxis verglichen. Der daraus resultierende Vergleich zeigt, dass die kompaktesten Modelle wiederum die besten praktischen Ergebnisse aufweisen.

Ship Traffic Optimization on the Kiel Canal: Formulations, Valid Cuts and Presentation of a Branch-&-Price Solution Method
Student/in: Jan M.H. Fischer
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Der Nord-Ostsee-Kanal oder auch Kiel Kanal genannt ist die am meisten befahrene Wasserstraße der Welt. Der Kanal ist in beide Richtungen befahrbar, an vielen Stellen aber einspurig, was die Routenplanung zu einer komplexen, bislang von Hand ausgeführten Aufgabe macht. Ich stelle in meiner Arbeit einen funktionierenden globalen Ansatz vor, der unter den bestehenden Lösungen im Schnitt mehrere Prozentpunkte an Gesamtwartezeit für die Reedereien einsparen kann. Es werden die Auswirkungen verschiedener Formulierungen diskutiert und zudem eine problemspezifische Vorverarbeitung und Stärkungen der Formulierung präsentiert. Ein neuer Ansatz versucht, gute Praxislösungen zu generieren und kann bei zusätzlicher Wartezeit von fünf Minuten pro Schiff eine Halbierung der Routenkomplexität bewirken. Schließlich stelle ich einen erweiterten Branch-&-Price Algorithmus für die Dantzig-Wolfe Reformulierung vor, der in Tests erfolgreich die MIP-Lösung einiger Instanzen übertrifft.

The prediction of sales in retail on the level of stock keeping units in the presence of promotions
Student/in: Maximilian Peters
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

The ability to predict future demand accurately is of essential importance in supply chain management. This includes the prediction of sales in retail during promotion periods, where the number of sales differs greatly compared to non-promotion periods. The goal of this master thesis is to increase the accuracy of stock keeping unit (SKU) sales prediction models during promotion periods in a retail setting. Different promotional factors, together with interaction effects between different articles on promotion and consequences of the COVID-19 pandemic are analysed to achieve this goal. This introduces challenges in the form of high dimensionality and sparsity, which are met with a multiple linear regression model. Besides an accurate prediction, which is achieved by the incorporation of these features, this model allows to draw conclusions about causal relations between the influencing factors and the number of sales. The model is applied to data provide by a Dutch supermarket to evaluate its performance.

The Temporal Facility Location Problem
Student/in: Daniel Bugdalle
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Location planning over a time horizon is a common task and therefore needs efficient solving methods. Experiments with temporal extensions to related problems indicate that branch-and-price algorithms might also be suitable for solving the temporal facility location problem (TFLP). This is supported by the reproduction of the results of two papers with related temporal problems, namely the temporal bin packing problem and the temporal knapsack problem. The knowledge obtained from these results is then used to create several TFLP instances with different parameter scenarios. The reproduction as well as the solving of the TFLP instances is performed with GCG and SCIP as branch-and-price and general-purpose solver respectively. In the experiments conducted in this thesis the instance parameter that has the biggest influence on the solving times is the opening cost, but having uncapacitated or capacitated facilities is another important factor. Comparing the results of GCG and SCIP on these scenarios leads to the conclusion that in most cases the general-purpose solver SCIP is the faster alternative. The branch-and-price solver GCG is useful for large instances with expensive opening cost and useful for some instances when the facilities are uncapacitated.

Vorraussagen Gemischt-ganzzahligen Problem-Klassen mithilfe Graph Neuronalen Netzen
Student/in: Stefan Seiler
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2021
Erstes Gutachten:
Zusammenfassung

Machine learning methods and deep learning in particular have seen many use-cases for almost every domain in the last couple of years now. Among those is the domain of discrete optimization. In discrete optimization machine learning has been applied to heuristically improve some algorithms. Since similar models in discrete optimization can also be handled or processed similarly, we will utilize Graph Convolutional Network (GCN) to predict which problem class a Mixed Integer Programm (MIP) belongs to, such that suitable algorithm can be applied to a model. To be exact, the natural variable-constraint bipartite graph representation of MIPs is utilized to train a GCN in the task of classification. The trained GCN will additionally be able to represent any MIP by a fixed size feature vector, which can be used to calculate how similar different MIPs are to each other. The process of training the GCN will be documented and our final model will be evaluated by comparing its performance to its competition. In addition to this, some experiments will be conducted to get a better understanding of which features and which parts of the networks are important for good classification results.

2020
Ein Vergleich von Modellierungsvarianten in einem Branch-and-Price-Ansatz zur Lösung des Schichtplanungsproblems an Flughäfen
Student/in: Christopher Schwanen
Studium: Wirtschaftswissenschaft |
Abschluss: M.Sc. |
Jahr: 2020
Erstes Gutachten:
Minimizing Airplane Boarding Time: The Assignment Problem of Seats and Carry-On Luggage Space
Student/in: Yannik Dietz
Studium: Wirtschaftsingenieurwesen FR Maschinenbau |
Abschluss: B.Sc. |
Jahr: 2020
Erstes Gutachten:
Zusammenfassung

In this bachelor thesis the optimasation of the airplane boarding process is investigated. Given is a set of cabin layouts and a set of passengers with different movement speeds and amounts of carry-on luggage. To improve the overall boarding time each seat has to be assigned to a passanger and each carry-on luggage space to a luggage. The passanger satisfaction sets further requirements to the boarding process. The assignment problem is formulated as a mixed integer problem (MIP) and differentiates itself from previous works by the direct optimisation of the overall boarding time, in combination with different numbers of carry-on luggage per passanger such as limitaions of the carry-on luggage space. To investigate the assignment problem, the formulated mathematical model such as developed heuristics are implemented. The experiments with different calculations show a strong correlation between the overall boarding time and the amount of carry-on luggage to stow in the carry-on luggage space in the airplane cabin. The best solution is achieved using the heuristic \(H_{wtw}^{v2}), giving excellent boarding times in addition to a high amount of stowed carry-on luggage reaching close to maximum values.

Robust and on-line approaches for the balanced charging problem under uncertainty
Student/in: Lena Brüggemann
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2020
Erstes Gutachten:
Zusammenfassung

Emissionsfreie Mobilität gewinnt immer mehr an Wichtigkeit. Für diese sind Elektrofahrzeuge unabdingbar, dadurch entstehen neue Fragen und Herausforderungen. Das iMove Projekt beschäftigt sich unter anderem mit dem „balancierten Ladeproblem (BCP)“. Hierbei wird eine Plattform entwickelt, die die Ladevorgänge von Elektrofahrzeugen optimal den Ladesäulen des Elektrische Netzes zuweisen soll. Optimalität ist bei diesem Problem zweigeteilt. Auf der einen Seite sollen die Wünsche der Elektrofahrzeugfahrer erfüllt werden. Auf der anderen Seite soll die Last auf das Elektrische Netz möglichst ausgeglichen bleiben. Hierfür wurde ein MIP entwickelt. Diese Masterarbeit beschäftigt sich mit dem Problem, dass die Elektrofahrzeugfahrer möglicherweise die Zuweisung zu einer Ladesäule der Plattform ignorieren und dieser nicht folgen. Während robuste Ansätze für diese Art der Unsicherheit nicht optimal geeignet scheinen, stellt es sich heraus das Online Ansätze eine gute Alternative bieten mit abweichenden Fahrern umzugehen. Die beste Güte erzielen Online Ansätze mit Unterstützung der Offline-Lösungen. Das Online-BCP ermöglicht es trotz abweichender Fahrer eine zulässige Lösung zu finden, allerdings zeigt sich, dass die Güte des Online-BCP noch ausbaufähig ist.

Robust Optimization of Industrial Production Scheduling Considering Demand Side Management
Student/in: Julius Mathews
Studium: Wirtschaftsingenieurwesen |
Abschluss: M.Sc. |
Jahr: 2020
Erstes Gutachten:
Zusammenfassung

The currently ongoing energy transition increases the share of renewable energies in the electricity mix. In Germany, this is covered in particular by wind and solar energy, which are considered volatile. Since a stable power grid must guarantee a balance between the electricity produced and the electricity demanded at all times, this development presents new challenges for electricity suppliers and grid operators. One approach to counteract the fluctuation in the energy supply network is demand-side management (DSM). DSM refers to the management of demand for network-based services by customers in industry, trade and private households. Electricity suppliers benefit from DSM by increasing the reliability of supply, while electricity consumers can reduce their energy costs benefiting from financial incentives. This Master's thesis investigates, with regard to demand-side management, how optimized production planning can reduce the energy costs of a general energy-intensive production process. For this purpose, a mixed-integer linear model is developed and set up. In particular, two new possibilities for cost reduction will be modeled: on the one hand, the exploitation of volatile electricity prices by load redistribution, on the other hand, the provision of balancing power. In production planning, the various framework conditions of the production process and uncertainties in some model parameters, such as the demand for balancing power, must be taken into account. Therefore, methods from the field of robust optimization are applied as a solution for the optimization problem.

Route Planning for Active Space Debris Removal
Student/in: Jonas Scheller
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2020
Erstes Gutachten:
Zusammenfassung

With an increasing number of man-made objects in space, the area around earth is getting increasingly polluted. Due to the chance of collisions, orbiting debris puts future missions at risk. The Kessler syndrome projects a cascading amount of debris collisions that result in an exponential increase of debris pieces. In order to avoid a catastrophic scenario, space agencies such as the European Space Agency propose missions for an active removal of space debris. Depending on the removal method, one mission aims to remove multiple debris objects. Thus, during the mission design, a combinatorial problem needs to be solved deciding the selection of debris objects and the order of space rendezvous. The problem setup shares similarities with a variant of the traveling salesman problem with city selection. The goal is to maximize the profit of the visited cities with a limited traveling budget. Since the debris orbits are exposed to perturbations, it is assumed that the costs of traveling between the objects are likely to change over time. This thesis will explore various mixed integer problem formulations for both constant costs and dynamic costs over time. For the static case, we are able to find optimal routes even for bigger debris clouds of more than 2000 objects. The proposed formulations for the dynamic case are able to solve large instances, when carefully selecting the time parameters. Moreover, we have implemented a genetic algorithm to further explore the solution space.

The Seat Assignment Problem for Aeroplane Boarding
Student/in: Jens Doveren
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2020
Erstes Gutachten: W. Unger
| Zweites Gutachten: M. Lübbecke
Zusammenfassung

In this thesis, we investigate possible optimisations of the aeroplane boarding process. To accomplish this, we define and mathematically model the process, formulate it as a minimisation problem, and propose a solution procedure.We show that the problem is computationally hard in a theoretical sense and investigate the quality of heuristic approaches as well as some of its online properties.

The boarding process is of particular interest for airlines to improve profitability as well as customer satisfaction. Since boarding policy changes pose a lower implementation barrier than buying new planes or making changes to existing infrastructure, advances in aeroplane boarding research have the potential to positively impact customers and airlines relatively immediately.

Download:
2019
Computational Analysis of Connected Subgraph Optimization Models
Student/in: Christian Plewnia
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2019
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: B. Peis
Persistency Property of Stable-Set-Problems and its Connection to Unconstrained Pseudo-Boolean Optimization
Student/in: Karl Stickler
Studium: Wirtschaftsingenieurwesen FR Maschinenbau |
Abschluss: M.Sc. |
Jahr: 2019
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Walter
2018
Application of Supervised Machine Learning algorithms in a Predictive Maintenance use case at BMW
Student/in: Andrea Scholten
Studium: Betriebswirtschaftslehre |
Abschluss: M.Sc. |
Jahr: 2018
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: G. Walther
Design and Training of Neural Networks using Mixed-Integer Optimization - a Feasibility Study
Student/in: Lukas Walbröl
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2018
Erstes Gutachten: B. Leibe
| Zweites Gutachten: M. Lübbecke
Zusammenfassung

This thesis aims to evaluate the boundaries of neural network training using
mixed-integer optimization. Neural networks are a powerful machine learn-
ing technique that is able to classify data non-linearly. This technique is
applied to a lot of different tasks. However, traditional approaches to neural
network training can get stuck in local minima, while algorithms exist that
solve a mixed-integer optimization problem optimally. The goal of this thesis
in the context of mixed-integer programming. We start by showing which
kind of activation functions can be expressed by a mixed-integer program
(MIP). After that variants of neural network training using mixed-integer
programming are presented and it is shown which activation functions can
be incorporated into these variants. Finally, we use a blackbox-solver to ap-
ply the resulting models to the parity function and evaluate the performance
of our approaches.

Evaluierung verteilter Optimierung zum Lösen von MILPs für das Energiemanagement in Stadtquatieren
Student/in: Corinna Buhlrich
Studium: Wirtschaftsingenieurwesen Fachrichtung Elektrische Energietechni |
Abschluss: M.Sc. |
Jahr: 2018
Erstes Gutachten: A. Monti
| Zweites Gutachten: M. Lübbecke
Optimal Connected Vertex Clustering
Student/in: Sebastian Krott
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2018
Erstes Gutachten: G. Woeginger
| Zweites Gutachten: M. Lübbecke
Zusammenfassung

We introduce an optimization problem on graphs called Connected Vertex Clustering Problem (CVCP). The input consists of a finite graph, arbitrary linear constraints to restrict the set of feasible clusters and a linear objective function. The expected solution is a vertex clustering that optimizes the objective under the condition that each cluster induces a connected subgraph and satisfies the custom constraints. Besides partitional clustering, i.e., node partitioning, the solution may also be restricted to packings or coverings of nodes. We show that this highly configurable problem is NP-hard and propose a branch-and-price method as a solution approach. The suggested method is implemented as a framework which is capable of solving arbitrary CVCP instances. The framework can easily be extended with new features due to its plug-in architecture. This allows to exploit the characteristics of specific variants of the CVCP in order to enhance the efficiency of the solution process. We evaluate the developed framework on a districting problem for the German federal elections and on the Odd Cycle Packing Problem.

Download:
2017
Entwicklung eines Algorithmus zum Clustering eines Graphen zur Vereinfachung des Lösens eines Multi Commodity Flow Problems
Student/in: Karl Stickler
Studium: Wirtschaftsignenieurwesen MB |
Abschluss: B.Sc. |
Jahr: 2017
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Schneider
Zusammenfassung
Die vorliegende Arbeit hat das Ziel, einen Algorithmus zu entwickeln, welcher die Knoten eines Graphen verschiedenen Clustern zuteilt. Dieser Graph wird hierbei aus einer logistischen Problemstellung des Transportes von Kraftfahrzeugen abgeleitet. Dies geschieht vor dem Hintergrund der Unterteilung eines Multi Commodity Flow Problems in mehrere kleinere Probleme, welche durch die einzelnen Cluster gebildet werden sowie durch die zwischen den Clustern verlaufenden Kanten des Graphen. Somit soll die zur Lösungsfindung des logistischen Problems benötigte Laufzeit verringert werden können. Hierfür wird zunächst ein Überblick über den derzeitigen Stand der wissenschaftlichen Diskussion zum Thema Clustering gegeben. Im Anschluss werden verschiedene Clusteringansätze hinsichtlich ihrer Anwendbarkeit auf das vorliegende Problem bewertet. Sodann sollen passende Ansätze ausgewählt und hieraus ein Algorithmus für das vorliegende Problem entwickelt, dargestellt und bewertet werden. Dieser Algorithmus wird zuletzt an verschiedenen Instanzen des der Arbeit zugrundeliegenden Problems getestet und die erzielten Ergebnisse analysiert.
Heuristics for the Energy Minimizing Vehicle Routing Problem
Student/in: Boris Lyubenov
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2017
Erstes Gutachten: P. Rossmanith
| Zweites Gutachten: M. Lübbecke
Zusammenfassung
The Energy Minimizing Vehicle Routing Problem (EMVRP) introduced by Kara and Yetis in 2007 is an extended version of the traditional Vehicle Routing Problem of transportation logistics. In this thesis we consider different algorithms, which heuristically solve the EMVRP in reasonable computation time. This thesis also includes a comparison between the proposed heuristics, which lays out the advantages and disadvantages of each one using different sets of test instances.
Machine Learning as a Decision Support for a Generic Column Generation Framework
Student/in: Simon Grubert
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2017
Erstes Gutachten: B. Leibe
| Zweites Gutachten: M. Lübbecke
Zusammenfassung

Dantzig-Wolfe (DW) reformulation is a well-known approach to produce strong dual bounds for Mixed-Integer Programs (MIPs). If a MIP has a special structure which can be exploited well by a DW reformulation the solver could be much faster on the reformulated model than on the original. Otherwise the solver may fail completely. Providing a strong DW reformulation typically requires enhanced knowledge about the underlying model structure of the MIP which makes an automatic reformulation without such knowledge difficult. Despite this problem there have been several approaches proposed which implement such an automatic DW reformulation process into a state-of the-art MIP solver, especially the Generic Column Generation (GCG) framework [1]. In such frameworks the detection of a decomposition that exploits the underlying model structure is one of the most important aspects. GCG for example uses different detectors that use heuristics and clustering algorithms to generate a set of possible decompositions. Recently supervised learning algorithms have been applied by Kruber et al. [2] to decide if a reformulation of the model should be solved (and also which if several have been detected) or if the original model should better be solved by a standard solver. These first promising results showed that machine learning could be a useful support in this decision process. Besides this single question there might be other decisions in the entire process that could also potentially benefit by the use of supervised machine learning.

MILP Optimization for the Design and Operation of a District Heating Network Energy System Based on Measured Data from a Holiday Village in Blatten-Belalp (Switzerland)
Student/in: Marten Fesefeldt
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2017
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: G. Walther
Zusammenfassung

In Zusammenarbeit mit dem Centre de recherches energetiques et municipales CREM, Martigny, Schweiz (https://www.crem.ch/).

Solving Large Multi Constraint Multi-Commoditiy Flow Problems by Decomposition on Commodities
Student/in: Frederik Schulz
Studium: Wirtschaftsignenieurwesen EET |
Abschluss: B.Sc. |
Jahr: 2017
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Schneider
Zusammenfassung

The bachelor thesis deals with solving multi-commodity flow problems. These kinds of problems occur in different everyday situations. For example, the transport of goods in distribution networks or the movement of messages in communication networks. In addition to the considerable size of these flow problems, which often occurs, there can be further complicating constraints on nodes, edges, or goods. In the context of the work, an alternative solution approach for minimal-cost multi-commodity flow problems, which is based for the most part on the computation of k-shortest paths, is developed. Based on optimally solved single-sink single-source single-commodity flow sub-problems, whose accumulated solutions are usually an inadmissible solution of the multi-commodity flow, the developed solution approach tries to obtain a feasible solution by rerouting the flow of edges that are infeasible in the original problem. The developed approach will be evaluated in a feasibility study based on a real use case, which is a time-expanded distribution network of an automobile manufacturer with limitations on edges and goods.

2016
Clustering algorithms to find special structures in matrices
Student/in: Igor Pesic
Studium: Informatik |
Abschluss: B.Sc. |
Jahr: 2016
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: B. Leibe
Download:
2015
An Adaptive Large Neighborhood Search Algorithm for the Tail Assignment Problem of Airlines
Student/in: Andreas Hottenrott
Studium: Wirtschaftsingenieurwesen |
Abschluss: M.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Lübbecke
Download:
Ansätze zur Lösung eines auf Kompaktheit fokussierten Gebietseinteilungsproblems am Beispiel der Wahlkreiseinteilung von Deutschland
Student/in: Heiko Samlowski
Studium: Betriebswirtschaftslehre |
Abschluss: M.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Bewertung von Löser-Technologien für Gemischt-Ganzzahlige Lineare Optimierung eines Dezentralen Energiesystems
Student/in: Fritz Arnold
Studium: Wirtschaftsingenieurwesen |
Abschluss: B.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A. Bardow
Optimal rescheduling in automotive industry
Student/in: Markus Kruber
Studium: Informatik |
Abschluss: M.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: W. Unger
Zusammenfassung

In der Automobilindustrie führen lange Lieferwege und das Prinzip der "Just-In-Time-Produktion" zu einem unflexibelen Produktionsplan für mehrere Wochen. Gleichzeitig ist die exakte Vorhersage von Kundenwünschen, bedingt durch das hohe Maß an Spezialisierung (Mass Customization), nahezu unmöglich. In Kombination mit laufzeittechnischen Anforderungen beschreiben diese Bedingungen ein herausforderendes Problem in der Praxis.

In dieser Abschlussarbeit wird unter Anderem ein Algorithmus vorgestellt, in welchem ganzzahlige lineare Programmierung dazu genutzt wird, die durchschnittliche Verkaufszeit eines Autos zu reduzieren. Der Algorithmus ist in der Lage, basierend auf einem existierenden Produktionplan, eine Umplanung zu berechnen, welche die strengen Lagereinschränkungen an der Fabrik und die Kundenwünsche respektiert und gleichzeitig das frühst mögliche Lieferdatum 
für den Kunden garantiert.

Download:
Room Assignment for Graduation Trip of Humboldt Gymnasium Solingen
Student/in: Jan Derkum
Studium: Betriebswirtschaftslehre |
Abschluss: B.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Lübbecke
Zusammenfassung
In dieser Abschlussarbeit soll ein Algorithmus implementiert werden, der für Schüler und Lehrer des Humboldt Gymnasiums Solingen eine zulässige Zimmerbelegung berechnet, die u.a. möglichst kostengünstig ist, also möglichst wenig Zimmer benötigt. Weitere Einschränkungen sind: - Jeder Schüler ist einem Haus und einem Zimmer zugeordnet. - Sowohl Mädchen und Jungen als auch Schüler und Lehrer schlafen getrennt. - Da in der Regel fünf Klassen auf vier Häuser verteilt werden, wird mindestens eine Klasse in mehr als einem Haus untergebracht werden müssen. Falls eine Klasse geteilt wird, soll sie auf maximal zwei Häuser verteilt werden. Eventuell wird die zu teilende Klasse vorher angegeben. - Die meisten Zimmer können mit zusätzlichen Betten ausgestattet werden. Die Anzahl der Zimmer soll minimiert werden unter der Berücksichtigung, dass die Zimmer nicht zu voll werden. Das fertige Progamm soll dem Benutzer ermöglichen Daten zu einlesen, Wünsche zu äußern (z.B. welche Klasse geteilt werden soll) und die Zimmerbelegung in einem anschaulichen Format auszuschreiben. Es werden Implementationskenntnisse in C/C++ benötigt.
The Consecutive Dinner Problem
Student/in: Britta Grimm
Studium: Wirtschaftswissenschaft |
Abschluss: M.Sc. |
Jahr: 2015
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: Grit Walther
Zusammenfassung
Das Consecutive Dinner Problem beschreibt die Tourenplanung bzw die Gruppenfindung für teilnehmende Teams. Jede Route muss aus genau drei Stationen bestehen: Vorspeise, Hauptspeise und Nachspeise. Des Weiteren muss jedes Team genau einen Gang der eigenen Route selber zubereiten. Eine Gruppe, die sich bei einem Gang trifft, muss aus genau drei Teams bestehen, die sich nicht schon vorher bzw auch nachher nicht nochmal treffen werden. Jedes Team hat die Möglichkeit einen Wunschgang zu nennen. Die Zielfunktion des Problems minimiert einerseits die Strecke, die jedes Team im Laufe des Abends zurücklegen muss, und andererseits maximiert die Anzahl an Teams, die ihren Wunschgang zugeteilt bekommen. Mögliche Erweiterungen des Modells enthalten Differenzierungen der Teams durch Alter und/oder Geschlecht um gemischtere/homogenere Gruppenkonstellation zu erhalten. Auch könnte die Anzahl der schon teilgenommenen Veranstaltungen mit einbezogen werden. In dieser Masterarbeit soll ein IP entwickelt werden, das das oben beschriebene Problem beschreibt. Außerdem soll ein Software Tool entwickelt werden, was das Consecutive Dinner Problem löst. Daher werden Kenntnisse in der mathematischen, ganzzahligen Optimierung und Implemenationskenntnisse in C/C++ oder Java benötigt.
2014
Covering Rectilinear Polygons by Rectangles
Student/in: Jaromil Najman
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
Zusammenfassung

In this Master Thesis we consider the problem of covering rectilinear polygons by the
minimum number of axis-parallel rectangles. This problem finds applications in the
fabrication of DNA chip arrays [Hannenhalli et al. 2002], in VLSI design, where the
rectilinear polygon is a chip that has to be covered by a huge number of rectangular
transistors.
Other applications are data compression and in particular image compression, where
large rectangular areas with the same color can be compressed into one pixel.

Download:
Development of the application for inventory management automation and optimization
Student/in: Pavlo Zhdanov
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
Download:
Entwicklung eines Software-Tools zur Analyse, Prognose und Bewertung der Prognosegüte von Zeitreihen im Strommarkt
Student/in: Nina Deeg
Studium: Wirtschaftswissenschaften |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
Download:
Ganzzahlige Optimierung für ein Zeitablaufsteuerungsproblem aus der Farbmittelindustrie
Student/in: Richard Spiegelberg
Studium: BWL |
Abschluss: B.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
Download:
Optimierte Einteilung der Wahlkreise für die Deutsche Bundestagswahl: Problemanalyse, Modelle, Algorithmen & Ergebnisse
Student/in: Sebastian Goderbauer
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Download:
Optimierung von dezentralen Enegieversorgungssystemen mit Branch-and-Price
Student/in: Georg Schneider
Studium: Wirtschaftswissenschaft |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A. Bardow
Zusammenfassung

This work evaluates whether optimization problems resulting from modelling the optimal synthesis, design and operation of a decentralized energy supply system have an embedded structure which can be exploited by decomposition methods in solution algorithms. The objective is to determine if the the accuracy and/or the problem size in terms of number of periods of time and number of units considered may be increased, as these are limited if the branch-and-bound method combined with the simplex method is used to solve the problems. A model of the problem is formulated as a mixed-integer linear program as proposed by Yokoyama et al. (2002) and Voll (2013). The model is analyzed and two embedded structures suitable for decomposition are identified.

The first structure emphasizes the independent operation and design of every component. The second structure emphasizes the design and operation of all components and focuses on the independence of every period of time considered. The model is reformulated using the Dantzig-Wolfe decomposition principle for both proposed embedded structures. A numerical study is conducted where the synthesis, design and operation of a fictional energy supply system is optimized by both the branch-and-bound method combined with the simplex method and by the branch-and-price method. A set of instances is created for different degrees of complexity in terms of the number of units and the number of periods of time considered.

The results show that the dual bounds obtained by solving the rootnode LP relaxation can be improved in comparison to the conventional solution approach, if the reformulation emphasizing independent components is utilized. The results provide no evidence on improvements on the considered test set for the reformulation emphasizing design and operation. For the case of an optimal solution computing times required to solve the considered instances of a test set are found to be reduced by utilizing the branch-and-price method and the reformulation emphasizing components, if identical components are considered in the energy supply system in comparison to the non-commercial solver SCIP.

Download:
Robuste Lokale Suche für das Job Shop Scheduling Problem
Student/in: Friederike Menge
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
Download:
Schleusen trotz Verspätung. Robuste Modelle, Algorithmen und Rechenstudien
Student/in: Ilja Schwanke
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Download:
Structure and Characterization of Popular Matchings
Student/in: Oliver Scheel
Studium: BWL |
Abschluss: B.Sc. |
Jahr: 2014
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: Britta Peis
Download:
2013
Die Auswirkungen verschiedener Preprocessing-Routinen und Branch-And-Cut-Frameworks auf das Lösungsverhalten der Time Bucket Formulation des Travelling Salesman Problems mit Zeitfenstern
Student/in: Stephan M.F. Beckhäuser
Studium: Betriebswirtschaftslehre |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
Download:
Die richtige Distributionslogistik als Wettbewerbsvorteil in der Nutzfahrzeugindustrie am Beispiel der Schmitz Cargobull AG
Student/in: Thorben Deckers
Studium: Betriebswirtschaftslehre |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: J. Schönberger
Ein Grammatik-basiertes Modell zur optimalen Planung von Universitäts-Stundenplänen
Student/in: Andreas Bil
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
Models for the Steiner Tree Packing Problem
Student/in: Michael Sausen
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: J. Derks
Zusammenfassung

The Steiner tree packing problem is a long studied problem in combinato-
rial optimization. In contrast to many other problems, where an enormous
progress has been made in the practical problem solving, the Steiner tree
packing problem remains very difficult. Most heuristics schemes are ineffec-
tive and even finding feasible solutions is already NP -hard. What makes this
problem special, is that in order to reach an overall optimal solution non-
optimal solutions to the underlying NP -hard Steiner tree problems must be
used. Any non-global approach to the Steiner tree packing problem is likely
to fail. Integer programming is currently the best approach for computing
optimal solutions.
The goal of this master thesis is to give a survey of models relating to the
Steiner tree packing problem from the literature. In addition, a closer look
at a model for the switchbox routing problem in VLSI-Design will be given.

Download:
Preprocessing-gestütztes Lösen des Vehicle Routing Problems mit Zeitfenstern mittels verschiedener IP-Formulierungen
Student/in: Alena Gridchina
Studium: Betriebswirtschaftslehre |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: H.-J. Sebastian
Download:
Robuste Terminvergabe im Krankenhaus unter unsicheren Behandlungspfaden
Student/in: Luisa Eickmeyer
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Download:
Separation of generic cutting planes in branch-and-price
Student/in: Jonas Witt
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Zusammenfassung

When reformulating a given mixed integer program by the use of classical Dantzig-Wolfe decomposition, a subset of the constraints is partially convexified, which corresponds to implicitly adding all valid inequalities for the associated integer hull. Since these inequalities are not known, a solution of the original linear programming (LP) relaxation which is obtained by transferring an optimal basic solution of the reformulated LP relaxation is in general not basic. Hence, cutting planes which are separated using a basis like Gomory mixed integer cuts are usually not directly applicable when separating such a solution.

Nevertheless, we can use some crossover method in order to obtain a basic solution which is nearby the considered non-basic solution and generate cutting planes for the basic solution using its basis information. These cutting planes might also the solution we originally wanted to separate. So far, this problem was only considered extensively by Range, who proposed the previously described approach including a particular crossover method. We present a modified crossover method and extend this procedure by considering additional valid inequalities strengthening the original LP relaxation. Furthermore, we provide the first full implementation of a separator like this and tested it on instances of several problem classes.

Download:
The vertex separation problem in bipartite graphs: A cycle-based algorithm
Student/in: Ina Hoffmann
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2013
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Lübbecke
Download:
2012
Ein Spaltengenerierungsansatz für die Zuordnung von Güterzügen
Student/in: Tuğba Güçlü
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Download:
Eine Heuristik zum Erkennen von Staircase-Strukturen in Matrizen
Student/in: Mathias Luers
Studium: N. N. |
Abschluss: Dipl |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
Download:
Erzeugen von Treppenstufenformen in Matrizen
Student/in: Christina Schoenen
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
Experiments on Vanderbeck’s generic Branch-and-Price scheme
Student/in: Marcel Schmickerath
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: A.M.C.A. Koster
Download:
Lineare Optimierung von Transportwegen und Aufbau einer Sendungsverfolgung im OBI-Logistiknetzwerk
Student/in: Florian Hillebrand
Studium: Wirtschaftswissenschaftliches Zusatzstudium |
Abschluss: M.Sc. |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
Optimierungsmodelle für das Project Scheduling mit Iterationen
Student/in: Christina van Megen
Studium: N. N. |
Abschluss: Dipl |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
Permutieren einer Matrix in Blockdiagonalform mittels Graph-Partitionierung
Student/in: Christian Kind
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2012
Erstes Gutachten: M. Lübbecke
Download:
2011
Algorithms for Detecting Block Structures in Matrices
Student/in: Michael Bastubbe
Studium: Techno- und Wirtschaftsmathematik |
Abschluss: Dipl |
Jahr: 2011
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: R. Möhring
Download:
Gesamtheitliche Prozesskettensimulation
Student/in: Mehmet Ali Sener
Studium: Wirtschaftsingenieurwesen EET |
Abschluss: B.Sc. |
Jahr: 2011
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Lübbecke
Primal Heuristics for Branch-and-Price Algorithms
Student/in: Christian Puchert
Studium: Mathematik |
Abschluss: M.Sc. |
Jahr: 2011
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
2010
A Branch-and-Price Approach for Resource Leveling
Student/in: Eamonn Thorsten Coughlan
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: R. Möhring
A cutting plane algorithm for graph coloring
Student/in: Lena Maria Schwan
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Analyse einer Heuristik zur Reihenfolgeplanung paralleler Maschinen
Student/in: Lars Bauer
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Atomic routing games on maximum congestion
Student/in: Ann-Kathrin Heyse
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Aufspannende Teilgraphen mit kürzesten Umwegen
Student/in: Christoph Werner Acker
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Bestimmung eines aufspannenden Baumes mit annähernd minimalen Max-Stretch
Student/in: Frank Borchert
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Bikriterielle kürzeste Wege Probleme: Algorithmen
Student/in: Sorana Goetzke
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: R. Möhring
Bikriterielle Kürzeste-Wege-Probleme: Theorie
Student/in: Maria Skoutarianou
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: R. Möhring
Effizienter Algorithmus für das beschränkte zweidimensionale Zuschneideproblem
Student/in: Benedikt Kehr
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Ein Approximationsalgorithmus für das metrische unkapazitierte Facility Location Problem
Student/in: Florian Uhl
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Ein Approximationsalgorithmus für die zeitliche Einteilung unabhängiger parallel laufender Maschinen
Student/in: Stefan Schwarzkopf
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Ein Branch-and-Price-Algorithmus für den Straßenwinterdienst
Student/in: Sarah Kirchner
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Flottenplanung von Flugzeugen
Student/in: Sebastian Erik Vock
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Ganzzahlige Programmierung für die Bestimmung der Dimension einer partiell geordneten Menge
Student/in: Katja Krüger
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Felsner
Gemischt-ganzzahlige Optimierung am Beispiel von Losgrößenproblemen
Student/in: Philipp Walter
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Generic Branch-Cut-and-Price
Student/in: Gerald Gamrath
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Grötschel
Download:
Modellieren und Lösen eines Gemischt-Ganzzahligen linearen Programms für die Erstellung eines kostenminimalen Luftverkehrsnetzes
Student/in: Tim Weisgerber
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
Train Timetabling Problem
Student/in: Dominique Achard
Studium: Mathematik |
Abschluss: B.Sc. |
Jahr: 2010
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: S. Ulbrich
Download:
2009
Winkelminimierung bei Überdeckungsproblemen in Graphen
Student/in: Olaf Maurer
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2009
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: R. Möhring
Download:
2008
Aspects of Quickest Multicommodity Flows
Student/in: Jens Hillmann
Studium: Mathematik |
Abschluss: Dipl |
Jahr: 2008
Erstes Gutachten: M. Lübbecke
| Zweites Gutachten: M. Skutella