Abschlussarbeiten

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.

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.

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.

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.

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.

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.