New Multiobjective Shortest Path Algorithms

**Thema der Dissertation:**New Multiobjective Shortest Path Algorithms

Generic Solution Methods and Representations for Multiobjective Combinatorial Optimization Problems

**Thema der Disputation:**Generic Solution Methods and Representations for Multiobjective Combinatorial Optimization Problems

In the first part of the talk we discuss two common techniques to solve MOCO problems: the weighted sum scalarization method and the ε-constraint method. These techniques produce single optimal solutions and they are most often used as subroutines to compute complete sets of optimal solutions for MOCO problems. I.e., they are often used in exact MOCO algorithms.

In the second part of the talk we discuss how to use the ε-constraint method to compute representations of minimal cardinality for MOCO problems with two objective functions. In addition, we give a strong intuition on why techniques used in such biobjective optimization settings often perform poorly in general multiobjective optimization.

**Abstract:**Multiobjective Combinatorial Optimization (MOCO) problems are often intractable, an issue that can make multiobjective modelling unappealing in practice. A promising approach to tackle this issue is to compute representations: a subset of the set of feasible solutions that builds a parametrized approximation of the set of optimal solutions. A representation’s parameters control the spacing between its elements and the quality of their elements w.r.t. the optimal solutions.In the first part of the talk we discuss two common techniques to solve MOCO problems: the weighted sum scalarization method and the ε-constraint method. These techniques produce single optimal solutions and they are most often used as subroutines to compute complete sets of optimal solutions for MOCO problems. I.e., they are often used in exact MOCO algorithms.

In the second part of the talk we discuss how to use the ε-constraint method to compute representations of minimal cardinality for MOCO problems with two objective functions. In addition, we give a strong intuition on why techniques used in such biobjective optimization settings often perform poorly in general multiobjective optimization.

### Time & Location

May 15, 2024 | 03:30 PM

Hörsaal

(Zuse-Institut Berlin, Takustr.7, 14195 Berlin)