Multicriteria linear optimisation with applications in sustainable manufacturing

dc.contributor.advisorBorndörfer, Ralf
dc.contributor.advisorSkutella, Martin
dc.contributor.authorSchenker, Sebastian
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeSkutella, Martin
dc.contributor.refereeBorndörfer, Ralf
dc.contributor.refereeRuzika, Stefan
dc.date.accepted2019-10-23
dc.date.accessioned2019-11-29T13:52:24Z
dc.date.available2019-11-29T13:52:24Z
dc.date.issued2019
dc.description.abstractMulticriteria 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.en
dc.description.abstractMehrkriterielle 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.de
dc.description.sponsorshipDFG, SFB 1026, Sustainable Manufacturing - Globale Wertschöpfung nachhaltig gestaltenen
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/10282
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-9244
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc510 Mathematikde
dc.subject.othermathematical optimisationen
dc.subject.otherlinear programmingen
dc.subject.otherinteger programmingen
dc.subject.otherlinear optimisationen
dc.subject.othermulticriteria optimisationen
dc.subject.othermathematische Optimierungde
dc.subject.otherlineare Programmierungde
dc.subject.otherganzzahlige Programmierungde
dc.subject.otherlineare Optimierungde
dc.titleMulticriteria linear optimisation with applications in sustainable manufacturingen
dc.title.translatedMehrkriterielle lineare Optimierung mit Anwendungen in nachhaltiger Produktionstechnikde
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
schenker_sebastian.pdf
Size:
1.6 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.9 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections