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.

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.

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.

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 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.

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.