Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-9244
Main Title: Multicriteria linear optimisation with applications in sustainable manufacturing
Translated Title: Mehrkriterielle lineare Optimierung mit Anwendungen in nachhaltiger Produktionstechnik
Author(s): Schenker, Sebastian
Advisor(s): Borndörfer, Ralf
Skutella, Martin
Referee(s): Skutella, Martin
Borndörfer, Ralf
Ruzika, Stefan
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Multicriteria optimisation is concerned with optimising several objectives simultaneously. Assuming that all objectives are equally important but conflicting, we are interested in the set of nondominated points, i.e., the image set of solutions that cannot be improved in any objective without getting worse off in another one. This thesis comprises three parts. The first part considers the computation of nondominated vertices of multicriteria linear programs. We present a cutting plane algorithm for finding nondominated vertices based on enumerating the vertices of a weight space polyhedron and describe its implementation in PolySCIP, a solver for multicriteria optimisation problems which we developed as a part of this dissertation. The focus of the second part is on multicriteria integer programs. In this part we investigate a partitioning of the set of nondominated points given by the set of points whose projections remain nondominated if one of the objectives is discarded and the set of points whose projections become dominated if one of the objectives is discarded. We present characteristics of this partitioning and show that the first mentioned partition can be used as an approximation of the entire set of nondominated points. The third part of this thesis considers two real-world applications in the context of sustainable manufacturing. The first problem regards bicycle frame manufacturing via a bicriteria integer programming formulation for which the non-dominated points are computed via PolySCIP. The second problem considers a tricriteria assignment problem in the context of scenario analysis. We classify this problem, show its hardness, and compute the set of nondominated points as well a partitioning of the set of nondominated points for given real-world data via PolySCIP.
Mehrkriterielle Optimierung befasst sich mit Optimierungsproblemen, bei denen mehrere in Konflikt stehende Zielfunktionen gleichzeitig optimiert werden. Unter der Annahme, dass alle Zielfunktionen gleichwertig sind, betrachten wir einen Bildpunkt als nicht-dominiert, sofern er in keiner Zielfunktion verbessert werden kann ohne sich in einer anderen Zielfunktion zu verschlechtern. In dieser Arbeit interessieren wir uns für die Menge der nicht-dominierten Punkte für ein gegebenes mehrkriterielles Optimierungsproblem. Diese Dissertation lässt sich in drei Teile gliedern. Der erste Teil beschäftigt sich mit dem Berechnen von nicht-dominierten Eckpunkten im Kontext mehrkriterieller linearer Programmierung. Nach einführenden Erläuterungen präsentieren wir einen Algorithmus, der auf der Enumeration von Eckpunkten eines Gewichtsraumpolyeders basiert. In diesem Zusammenhang beschreiben wir ebenfalls die zugehörige Implementation in PolySCIP, einem von uns entwickelten Löser für mehrkriterielle Optimierungsprobleme. Der zweite Teil dieser Arbeit beschäftigt sich mit mehrkriterieller ganzzahliger Programmierung. In diesem Teil untersuchen wir eine Partitionierung der nicht-dominierten Punkte in zwei Teilmengen. Die erste Partition beinhaltet alle nicht-dominierten Punkte, deren Projektion nicht-dominiert bleibt, sofern man eine Zielfunktion außer Betracht lässt. Die zweite Partition beinhaltet alle nicht-dominierten Punkte, deren Projektion dominiert wird, sofern man eine Zielfunktion außer Betracht lässt. Wir charakterisieren diese Partitionierung und zeigen, dass die erstgenannte Partition die Menge der nicht-dominierten Punkte approximiert. Der dritte Teil dieser Arbeit betrachtet zwei Anwendungen aus dem Bereich der nachhaltigen Produktion. Die erste Anwendung betrifft ein auf Fahrradrahmen bezogenes Produktionsproblem, welches als ganzzahliges Programm mit zwei Zielfunktionen modelliert wird. Für die gegebenen Instanzen berechnen wir die Menge der nicht-dominierten Punkte mittels PolySCIP und interpretieren die zugehörigen Resultate. Die zweite Anwendung betrifft ein Optimierungsproblem mit drei Zielfunktionen aus dem Bereich der Szenarioanalyse. Wir zeigen, dass es zur Klasse der NP-schweren Probleme gehört und berechnen die Menge der nicht-dominierten Punkte sowie die zugehörigen Partitionen für die gegebenen Instanzen ebenfalls mittels PolySCIP.
URI: https://depositonce.tu-berlin.de/handle/11303/10282
http://dx.doi.org/10.14279/depositonce-9244
Exam Date: 23-Oct-2019
Issue Date: 2019
Date Available: 29-Nov-2019
DDC Class: 510 Mathematik
Subject(s): mathematical optimisation
linear programming
integer programming
linear optimisation
multicriteria optimisation
mathematische Optimierung
lineare Programmierung
ganzzahlige Programmierung
lineare Optimierung
Sponsor/Funder: DFG, SFB 1026, Sustainable Manufacturing - Globale Wertschöpfung nachhaltig gestalten
License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
File Description SizeFormat 
schenker_sebastian.pdf1.64 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons