Abschlussarbeiten
Sie möchten Ihre Abschlussarbeit in Operations Research oder mathematischer Optimierung schreiben? Hier finden Sie Themen und Wissenswertes.
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 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
Im Artikel
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.
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.
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.
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.
In ihrem Paper Combinatorial Attacks on Binarized Neural Networks betrachten die Autoren "Attacken" auf binarisierte neuronale Netze (die Gewichte sind nur 0 oder 1). Eine "Attacke" ist eine kleine Veränderung in den Daten, so dass das Netz falsch (zB) klassifiziert. Im genannten Paper wird zum Auffinden solcher Attackend ein gemischt-ganzzahliges Programm vorgeschlagen, das aber für große Eingabedaten nicht mehr in akzeptabler Zeit rechnet. Inhalt dieser Arbeit ist eine andere Modellierung, eine Implementation ggf. eines Branch-and-Price Algorithmus und ein experimenteller Vergleich gegen den genannten Ansatz. Falls erfolgreich, kann aus dieser Masterarbeit eine wissenschaftliche Veröffentlichung werden.
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.
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.
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.
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.
Standortplanung ist ein klassisches OR Problem. Aus einer Menge potenzieller (ggf. kapazitierter) Standorte muss eine Auswahl geöffnet werden; Kunden müssen so geöffneten Standorten zugewiesen werden, dass die Kapazitäten der Standorte eingehalten werden. In dieser Arbeit betrachten wir die Erweiterung, dass nicht alle Kunden immer an einen Standort angebunden werden müssen, sondern jeweils nur in einem (bekannten) Zeitintervall. Die neue Restriktion ist, dass zu keinem Zeitpunkt die Kapazität jedes Standorts überschritten werden darf.
Eine Motivation für diese Erweiterung ist die Standortplanung von Ladesäulen für E-Fahrzeuge. Die (strategische) Entscheidung der Standortwahl mischt sich mit dem (operativen) Bedarf. In der Literatur gibt es bereits eine zeitliche Erweiterung des Knapsack-Problems, sowie ein zeitliche Erweiterung des Bin Packing Problems. Beide werden mit Hilfe von Branch-and-Price Algorithmen gelöst, das wird voraussichtlich auf für die zeitliche Erweiterung des Facility Location Problems sinnvoll sein. Diesen Ansatz basierend auf der Literatur zu konzipieren, zu implementieren und experimentell zu testen ist Inhalt dieser Arbeit.
Ausgewählte abgeschlossene Arbeiten
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.
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.
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.
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.
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.
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.
In Zusammenarbeit mit dem Centre de recherches energetiques et municipales CREM, Martigny, Schweiz (https://www.crem.ch/).
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.
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.
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.
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.