Im Oberseminar der Arbeitsgruppe Optimierung

am 17.01.2023
um 17:15 Uhr
in 48-208

wird Levin Nemesch von der Universität Osnabrück zu Gast sein und einen Vortrag über TriPoD: Tri-Objective Polynomial Delay - Implementing and Refining a New Algorithm for TOLPs halten. Interessierte Gäste sind herzlich willkommen.

Abstract:

In multi-objective optimization (MOO), the goal is to optimize several objectives for a problem at the same time. As a consequence, not one single solution is simply "optimal" anymore. We look for the set of Pareto-optimal solutions instead. One specific subproblem of MOO is Tri-Objective Linear Programming (TOLP). In 2022, the first algorithm with polynomial delay for extreme points of TOLP was presented by Fritz Bökler. This presentation is about a master's thesis in which this algorithm is implemented and developed further. TriPoD is the name of the resulting software and stands for Tri-Objective Polynomial Delay. As the thesis is still ongoing, many practical results are intermediary.

The first part of the presentation gives an introduction into MOO and Bökler's new algorithm. Then, we look at the state of the art for practical TOLP solving and compare the performance of the new algorithm to established solvers. This leads us to a refinement of the algorithm: We trade polynomial delay for polynomial space. The polynomial space algorithm introduces the opportunity to parallelize the algorithm. As no current state-of-the-art solver is able to efficiently use parallel computing, this might open completely new possibilities in the future