Multikriterielle gemischt-ganzzahlige Optimierungsprobleme treten in einer Vielzahl von Anwendungsgebieten auf. Beispiele dafür sind Portfoliomanagement, sowie Ablauf- und Anlagenplanung. Häufig haben diese Optimierungsprobleme eine hohe Anzahl an Variablen und eine relativ geringe Anzahl an Zielfunktionen. In dieser Arbeit werden drei neue, deterministische Ansätze zur Approximation der nichtdominierten Menge solcher Optimierungsprobleme vorgestellt. Zwei der Ansätze arbeiten fast vollständig im Bildbereich. Dies hat den Vorteil, dass ihre Performance nur geringfügig durch die hohe Anzahl an Variablen beeinflusst wird, die häufig in Anwendungsproblemen auftritt. Während es sich bei einem der Ansätze um ein allgemeines Framework handelt, das nicht immer praktisch und algorithmisch realisiert werden kann, ist der andere Ansatz in der Lage, nahezu jedes multikriterielle gemischt-ganzzahlige konvexe Optimierungsproblem theoretisch und auch praktisch zu lösen. Der dritte vorgestellte Ansatz erlaubt darüber hinaus auch die Lösung multikriterieller gemischt-ganzzahliger nichtkonvexer Optimierungsprobleme. Alle drei Ansätze gehören zu den ersten, die multikriterielle gemischt-ganzzahlige Optimierungsprobleme lösen können und Garantien für die Qualität der von ihnen berechneten Approximation geben. Numerische Tests und Auswertungen für alle drei Ansätze werden ebenfalls in dieser Arbeit vorgestellt. Alle drei Ansätze verwenden dasselbe Konzept einer Einhüllung (enclosure) zur Approximation der nichtdominierten Menge. Deren Berechnung kombiniert Techniken der ganzzahligen und der multikriteriellen kontinuierlichen Optimierung. Darüber hinaus nutzt der Ansatz für gemischt-ganzzahlige konvexe Optimierungsprobleme gezielt die gemischt-ganzzahlige Struktur des Optimierungsproblems aus. Es ist der erste Ansatz, der gleichzeitig mit einer gemischt-ganzzahligen linearen Relaxierung und einer Zerlegung in kontinuierliche konvexe Teilprobleme arbeitet.
Multi-objective mixed-integer optimization problems arise in a wide variety of practical applications. Examples include portfolio management, scheduling, and distribution planning. Usually, these optimization problems are characterized by a large number of variables and a relatively small number of objective functions. This thesis presents three new deterministic approaches to approximate the nondominated set of such optimization problems. Two of them operate almost entirely in the criterion space. As a result, their computational performance is only weakly affected by the large number of variables usually encountered in practical optimization problems. While one of the approaches is a rather general algorithmic framework that is not always applicable in practice, the other one is able to solve almost all kinds of multi-objective mixed-integer convex optimization problems both theoretically and practically. For multi-objective mixed-integer nonconvex optimization problems, a third approach is presented. All three approaches are among the first to solve multi-objective mixed-integer optimization problems and provide guarantees on the quality of the approximation that they compute. Numerical tests and evaluations of all of them are also presented in this thesis. All three approaches use the same concept, called enclosure, to approximate the non-dominated set. Its computation combines concepts from multi-objective integer optimization and multi-objective continuous optimization. In addition, the approach for multi-objective mixed-integer convex optimization problems explicitly explores the mixed-integer structure of the optimization problem and combines techniques from multi-objective continuous and single-objective mixed-integer optimization. It is the first of its kind to simultaneously work with and make use of a multi-objective mixed-integer linear relaxation and a multi-objective continuous convex decomposition of the overall multi-objective mixed-integer convex optimization problem.
Use and reproduction:
All rights reserved