Im Oberseminar der Arbeitsgruppe Optimierung

am 25.10.2022
um 17:15 Uhr
in 48-208

wird Alexandre D. Jesus von der Universität Coimbra zu Gast sein und einen Vortrag zum Thema Theoretical Model of Anytime Performance for Bi-Objective Optimization halten. Interessierte Gäste sind herzlich willkommen.

Abstract:
Anytime algorithms, which allow a practitioner to trade-off execution time for solution quality, are of particular interest in multi-objective optimization where it is often infeasible to identify all efficient solutions. In this talk, we will discuss a theoretical model that, under some mild assumptions, characterizes the ideal trade-off between execution time and solution quality, measured in terms of hypervolume, of anytime algorithms for bi-objective optimization that collect (efficient) solutions sequentially. We consider this ideal trafe-off under the assumption that the ideal goal of such a sequential algorithm is to maximize the hypervolume each time a solution is collected. We validate our model on benchmark knapsack problems against an oracle that has complete knowledge of the non-dominated set. The empirical results suggest that our theoretical model approximates the behavior of this optimal model quite well. We also show that our model can be used to guide an epsilon-constraint algorithm in order to achieve close to ideal anytime performance.