The goal in optimisation is to find parameter values that maximise (or minimise) a given objective function. Examples for classical combinatorial optimisation problems are the Minimum Spanning Tree problem~(MST), the Single-Source Shortest Path Problem~(SSSP) or the Travelling Salesperson Problem~(TSP) all of which have obvious and important applications, e.g., in logistics and vehicle routing. In practise however, we are rarely faced with problems with a single objective function. Instead, there are several objectives that require simultaneous optimisation: imagine each edge of an input instance to the aforementioned graph problems having two or more weights per edge. Than the component-wise summation of the edge-weights yields a problem with multiple objective function. In the domain of Multi-Objective Optimisation~(MOO) these objectives are usually conflicting and there is no single global optimum. Instead there is a set of so-called trade-off solutions that we aim to calculate. Unfortunately, but not surprising, multi-objective problems are usually harder than their single-objective counterparts. In fact, the multi-objective MST and SSSP are NP-hard. Moreover, the solution set can be exponentially large leading to intractability problems. In this seminar we will learn about algorithmic approaches to tackle multi-objective continuous and combinatorial optimisation problems. A sample of the topics: exact approaches, scalarisation methods, heuristic algorithms with no performance guarantees, but strong success in the wild. We will also dive into tackling multi-objective problems in the field of (Automated) Machine Learning and (Automated) Artificial Intelligence.
This block seminar course will be held in English, towards the end of 2023/2024 winter semester. Enrolment is restricted to at most 20 Bachelor or Master students, preferably with a background in (heuristic) optimisation. Students will work in groups of at most two on different MOO-related topics.. Each group will be assigned a paper from the research literature, which will serve as the starting point for an in-depth investigation of a specific topic. The results of this investigation will be presented in class and compiled into a report.
Preferably students should have a background in algorithms and (heuristic) optimisation.
Registration to the seminar is handled via the SuPra system.
Prof. Dr. Holger H. Hoos
Chair Holder, Alexander von Humboldt Professor
E-mail: hh[at]aim[dot]rwth-aachen[dot]de
Phone: +49 241 80 21451
Dr. Jakob Bossek
Assistant Professor (Akademischer Rat)
E-mail: bossek[at]aim[dot]rwth-aachen[dot]de
Phone: +49 241 80 21453
