h1

%0 Thesis
%A Gersing, Timo
%T Algorithms for robust combinatorial optimization with budgeted uncertainty and fair planning of the out-of-hours service for pharmacies
%I RWTH Aachen University
%V Dissertation
%C Aachen
%M RWTH-2024-05270
%P 1 Online-Ressource : Illustrationen
%D 2024
%Z Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
%Z Dissertation, RWTH Aachen University, 2024
%X Practical problems usually require robust or fair solutions. However, optimal solutions for classical optimization problems tend to structurally neglect these two criteria. This is due to the promotion of extreme decisions that exhaust the planning constraints and most profitable options as far as possible. Robustness, though, is usually achieved by spreading risks, and fairness by distributing benefits and burdens, which requires diverse solutions rather than extreme ones. Accordingly, both criteria often have to be explicitly integrated into optimization problems. This poses a challenge both from a modeling and an algorithmic point of view. In this thesis, we want to contribute to overcoming this challenge by studying the following problems. In the first part of this thesis, we consider robust optimization with budgeted uncertainty, which is one of the most popular approaches for addressing uncertainty in optimization problems. Positive complexity results as well as the existence of a compact reformulation for (mixed-integer) linear programs suggest that these problems are easy to solve. However, the reformulation as well as the algorithms that provide these complexity results do not perform well when solving robust combinatorial problems in practice. To address this, we propose a new class of valid inequalities to strengthen the reformulation. These inequalities are facet-defining in many cases, and are thus among the theoretically strongest inequalities. Furthermore, we develop a branch-and-bound algorithm based on new formulations and structural results. We show in two extensive computational studies that both approaches facilitate the computation of optimal robust solutions. Especially the branch and bound algorithm outperforms all previous approaches by far. In the second part, we consider the problem of planning the out-of-hours service for pharmacies, which ensures a continuous supply of pharmaceuticals. The problem consists in assigning 24-hour shifts to a subset of pharmacies on each day such that an appropriate supply is guaranteed while the burden on pharmacists is minimized. We present a model for the planning, developed in collaboration with the Chamber of Pharmacists North Rhine, and show that computing a feasible plan is NP-hard. We develop algorithms that nevertheless compute almost optimal plans for the North Rhine area in short time. The computed plans assign fewer shifts in total compared to the real plan of the Chamber of Pharmacists North Rhine, but they exhibit an unfair concentration of shifts. Consequently, we discuss strategies to integrate fairness into the planning. We show theoretical results on fairness in optimization problems, on the basis of which we compute out-of-hours plans that are almost maximally fair.
%F PUB:(DE-HGF)11
%9 Dissertation / PhD Thesis
%R 10.18154/RWTH-2024-05270
%U https://publications.rwth-aachen.de/record/986555