Abschlussarbeiten

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

63
Abschlussarbeiten

Das Wichtigste in Kürze

Sie studieren Mathematik, Informatik, 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 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
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.

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.

Optimal Production Planning in Selective Laser Melting
Abschluss: M.Sc.
Kontakt: M. Lübbecke
Details

In der additiven Fertigung mittels Lasertechnik fahren ein oder mehrere Laser eine Fläche ab, halten an verschiedenen Punkten und belichten das darunter liegende Material. Es kommen in der Prozessplanung zurzeit verschiedene Heuristiken zum Einsatz. Zunächst werden die Haltepunkte der Laser bestimmt, auf diesen Haltepunkten eine (oder mehrere) Touren bestimmt und dann die einzelnen zu belichtenden Positionen den verschidenen Lasern zugeordnet. Die mehrstufige hierarchische und darüber hinaus heuristische Planung verschwendet Potenzial. In dieser Arbeit soll dieses Potenzial ausgelotet werden, in dem für die einzelnen Planungsschritte exakte Optimierungsverfahren zum Einsatz kommen sollen und zusätzlich ein Optimierungsmodell nebst (schnellem) Lösungsansatz für die integrierte Planung des gesamten Prozesses entwickelt und implementiert werden.

Sehr gute Kenntnisse in ganzzahliger Optimierung und sehr gute Programmierkenntnisse (idealerweise in C/C++) sind unverzichtbar,  Erfahrungen mit dem SCIP Framework sind wünschenswert.

Die Arbeit ist in Kooperation mit dem Fraunhofer ILT.

Ausgewählte abgeschlossene Arbeiten

 

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