This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

Die Optimierung spielt in der Industrie und Technik eine entscheidende Rolle. Für einen Betrieb ist es beispielsweise äußerst wichtig, die zur Verfügung stehenden Ressourcen optimal zu nutzen und Betriebsabläufe effizient zu gestalten. Damit diese Vorhaben umgesetzt werden können, setzt man Methoden der Optimierung ein. Die Zielstellungen werden als eine abstrakte mathematische Aufgabe formuliert und anschließend wird versucht, dieses Problem mit einem Optimierungsverfahren zu lösen. Da die Komplexität der Problemstellungen in der Praxis ansteigt, sind exakte Verfahren in der Regel nicht mehr effizient anwendbar, sodass andere Methoden zum Lösen dieser Aufgaben entwickelt werden müssen, die in angemessener Zeit eine akzeptable Lösung finden. Solche Methoden werden als Approximationsalgorithmen bezeichnet. Im Gegensatz zu den exakten Verfahren ist der Verlauf der Optimierung bei dieser Verfahrensklasse vom Zufall abhängig. Dadurch lassen sich in der Regel keine Konvergenzaussagen beweisen. Dennoch hat sich gezeigt, dass Approximationsalgorithmen viel versprechende Ergebnisse für eine Vielzahl von unterschiedlichen Problemstellungen liefern. Zwei Approximationsalgorithmen werden in dieser Arbeit vorgestellt, untersucht und erweitert. Zum einen steht ein Verfahren im Vordergrund, welches aus Beobachtungen in der Natur entstanden ist. Es gibt Lebewesen, die durch verblüffend einfache Strategien in der Lage sind, komplexe Probleme zu lösen. Beispielsweise bilden Fische Schwärme, um sich vor Fressfeinden zu schützen. Der Fischschwarm kann dabei als selbstorganisierendes System verstanden werden, bei dem die Aktivitäten der einzelnen Fische hauptsächlich von den Bewegungen der Nachbarfische abhängig sind. An diesem erfolgreichen Schwarmverhalten ist der moderne Approximationsalgorithmus der Partikelschwarmoptimierung angelehnt. Weiterhin wird ein ersatzmodellgestütztes Verfahren präsentiert. Der Ausgangspunkt dieses Optimierungsverfahrens ist der Aufbau von Ersatzmodellen, um das Verhalten der Zielfunktionen anhand der bisherigen Auswertungen vorhersagen zu können. Damit so wenig wie möglich Funktionsauswertungen vorgenommen werden müssen, wird bei diesem Verfahren ein hoher Aufwand in die Wahl der Punkte investiert, welche auszuwerten sind. Die vorliegende Diplomarbeit gliedert sich wie folgt. Zunächst werden die mathematischen Grundlagen für das Verständnis der weiteren Ausführungen gelegt. Insbesondere werden multikriterielle Optimierungsaufgaben betrachtet und klassische Lösungsansätze aufgezeigt. Das dritte Kapitel beschäftigt sich mit der Partikelschwarmoptimierung. Dieser „naturanaloge Approximationsalgorithmus“ wird ausführlich dargelegt und analysiert. Dabei stehen die Funktionsweise und der Umgang mit mehreren Zielen und Restriktionen im Vordergrund der Ausarbeitung. Ein ersatzmodellgestütztes Optimierungsverfahren wird im Anschluss darauf vorgestellt und erweitert. Neben der Verfahrensanalyse, ist die Behebung der vorhandenen Schwachstellen ein vorrangiges Ziel dieser Untersuchung. Die eingeführten und implementierten Verfahren werden im fünften Kapitel an geeigneten analytischen und technischen Problemen verifiziert und mit anderen Approximationsalgorithmen verglichen. Anschließend werden Empfehlungen für die Verwendung der Verfahren gegeben. Die gewonnenen Kenntnisse werden im letzten Kapitel zusammengefasst und es wird ein Ausblick für zukünftige Forschungsthemen gegeben

Helmut-Schmidt-Univ./Univ. der Bundeswehr, Diss.--Hamburg, 2005.

Stuttgart, Univ., Diss., 2002.

Zugl.: Clausthal, Techn. Univ., Diss., 2008

In this thesis we consider optimization problems with complementarity constraints in infinite-dimensional spaces. On the one hand, we deal with the general situation, in which the complementarity constraint is governed by a closed convex cone. We use the local decomposition approach, which is known from finite dimensions, to derive first-order necessary optimality conditions of strongly stationary type. In the non-polyhedric case, stronger conditions are obtained by an additional linearization argument. On the other hand, we consider the optimal control of the obstacle problem. This is a classical example for a problem with complementarity constraints in infinite dimensions. We are concerned with the control-constrained case. Due to the lack of surjectivity, a system of strong stationarity is not necessarily satisfied for all local minimizers. We identify assumptions on the data of the optimal control problem under which strong stationarity of local minimizers can be verified. Moreover, without any additional assumptions on the data, we show that a system of M-stationarity is satisfied provided that some sequence of multipliers converges in capacity. Finally, we also discuss the notion of polyhedric sets. These sets have many applications in infinite-dimensional optimization theory. Since the results concerning polyhedricity are scattered in the literature, we provide a review of the known results. Furthermore, we give some new results concerning polyhedricity of intersections and provide counterexamples which demonstrate that intersections of polyhedric sets may fail to be polyhedric. We also prove a new polyhedricity result for sets in vector-valued Sobolev spaces.

Continues Integration has been a vital part of software development process in order to make the development process fast and reliable. There are number of actors which play an important role with support of third party tools that helps the development process to be effective and productive in nature. The CI- toolchain is capable of doing much more than the compilation of the software project which covers the daily life tasks of the developers like testing, documentation etc. The important part of automated toolchain is the conversion of source code artifacts into executables with the help of the build system. The selection of proper build system is a matter of subjective in nature and it depends upon the number of factors that should be analyzed before proceeding forward towards the selection mechanism. This thesis focuses on software rebuilding and proves practically with experiments that could help developers and managers to decide between two important software build systems SCons and CMake. It has been experimentally proved that what are the conditions and situations where SCons performs better and what are the moments where it is wise to select CMake as a build tool. At first, individual build tools are evaluated in terms of scalability, conveniency, consistency, correctness, performance (in terms of speed and targets) and later, the build systems are experimented by automating the workflow by increasing the source code artifacts to evaluate the performance when there is limited user interaction. The behavior of the build systems are also tried with other third party tools like Tessy for testing purposes, Jenkins as CI server, and Polarion as requirement engineering tool to show how much effort is required to integrate third party tools with the build system in order to increase the functionality. The evaluation of the build systems is important because that will highlights the areas where potential candidates are better and where there is lack of functional specifications. Generally speaking, SCons has an advantage of being Pythonic in nature and provides the developer ease of use to specify the build configurations using programmatic skills. CMake on other hand are on top of shelves where there is no need to understanding and caring about the underlying platform and where developers want to generate the native build tool solutions which are readily available for exporting them into IDEs. Though both of the build systems has different goals, for example SCons is ready to sacrifices the performance while providing user correctness of the build while CMake focuses on generating native build tools by understanding the underlying platform. All of these types of situations are discussed with experiments in this thesis and serves as the practical guides for high level managers to decide the build tools among others. After evaluation, this thesis firstly suggests the general techniques where the bottlenecks could be covered and then build tool specific optimizations and recommendations are discussed to speed-up the development process.

In der Arbeit werden Zwei-Ebenen-Optimierungaufgaben mit einer nichtkonvexen Zielfunktion in der unteren Ebene betrachtet. Dazu werden die bekannten Begriffe der optimistischen und pessimistischen Lösung erweitert, um auch so genannte stationäre Lösungen zu definieren, deren Existenz unter schwächeren als den bisher geläufigen Halbstetigkeitsbedingungen gezeigt werden kann. Für den Fall der einparametrischen Zwei-Ebenen-Optimierung wird abschließend eine Verallgemeinerung des von Jongen, Jonker und Twilt eingeführten Generizitätsbegriffes vorgeschlagen, dessen Verwendung die numerische Behandlung solcher Aufgaben realisierbar macht.

Die Arbeit thematisiert die Optimierung von Beschichtungsvorgängen mithilfe der Ionenstrahlsputterdeposition hinsichtlich der Homogenität von Substraten mit Tiefenprofil. Dazu wurde eine Simulationssoftware entwickelt und hinsichtlich der Problemstellung an mehreren Beispielen getestet.

In der Motorenentwicklung treten Optimierungsprobleme auf, die sich nur schwer mit klassischen Methoden der Optimierung lösen lassen. Daher untersucht diese Arbeit nichtlineare Verfahren der ein- und multikriteriellen Optimierung, die unter Einhaltung nichtlinearer Nebenbedingungen mit relativ wenigen Funktionswertberechnungen in der Lage sind globale Extrema zu finden. Vorgestellt werden ein Genetischer Algorithmus und zwei Ersatzmodell-gestützte Optimierungsverfahren, die in das Optimierungsmodul der IAV EngineeringToolbox integriert wurden. Die Tauglichkeit der Algorithmen wurde an technischen Beispielen (1D-Strömungssimulation, Kettentriebsoptimierung), sowie an geeigneten Testfunktionen überprüft.