# Multicriteria linear optimisation with applications in sustainable manufacturing

## Schenker, Sebastian

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.