Algorithms for robust combinatorial optimization with budgeted uncertainty and fair planning of the out-of-hours service for pharmacies

Gersing, Timo; Koster, Arie Marinus; Büsing, Christina Maria Katharina; Pferschy, Ulrich

doi:43283

Algorithms for robust combinatorial optimization with budgeted uncertainty and fair planning of the out-of-hours service for pharmacies = Algorithmen zur robusten kombinatorischen Optimierung mit budgetierter Unsicherheit und zur fairen Planung von Apothekennotdiensten

Gersing, Timo^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Timo Gersing, M.Sc.

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Büsing, Christina Maria Katharina (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH* ; Pferschy, Ulrich (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-05-17

Online
DOI: 10.18154/RWTH-2024-05270
URL: https://publications.rwth-aachen.de/record/986555/files/986555.pdf

Einrichtungen

Projekte

BMBF 05M16PAA - Verbundprojekt 05M2016 - HealthFaCT: Optimierung der ambulanten medizinischen Versorgung im ländlichen Raum - Teilprojekt 3 (BMBF-05M16PAA) (BMBF-05M16PAA)

Inhaltliche Beschreibung (Schlagwörter)
branch and bound (frei) ; fairness (frei) ; pharmacies (frei) ; polyhedral combinatorics (frei) ; robust optimization (frei) ; shift planning (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Praktische Probleme erfordern meist robuste oder faire Lösungen. Optimale Lösungen für klassische Optimierungsprobleme neigen allerdings dazu diese beiden Kriterien strukturell zu vernachlässigen. Ursächlich hierfür ist die Begünstigung extremer Entscheidungen, welche die Planungsbedingungen und rentabelsten Optionen weitestmöglich ausschöpfen. Robustheit wird in der Regel jedoch durch eine Streuung von Risiken sowie Fairness durch eine Verteilung von Nutzen und Lasten erreicht, was eher diverse Lösung anstelle extremer erfordert. Beide Kriterien müssen entsprechend oftmals explizit in Optimierungsprobleme integriert werden. Dies stellt sowohl aus Sicht der Modellierung als auch der Algorithmik eine Herausforderung dar. In dieser Arbeit wollen wir mit dem Studium der folgenden Probleme einen Teil zur Bewältigung dieser Herausforderung beitragen. Im ersten Teil dieser Arbeit betrachten wir robuste Optimierung mit budgetierter Unsicherheit, einen der populärsten Ansätze zur Berücksichtigung von Unsicherheiten in Optimierungsproblemen. Positive Komplexitätsresultate sowie die Existenz einer kompakten Reformulierung für (gemischt ganzzahlige) lineare Programme suggerieren, dass diese Probleme leicht zu lösen sind. Allerdings zeigen die Reformulierung und die Algorithmen, welche diese Komplexitätsergebnisse liefern, in der Praxis keine gute Performanz beim Lösen robuster kombinatorischer Probleme. Um dem entgegenzuwirken, präsentieren wir eine neue Klasse gültiger Ungleichungen zur Stärkung der Reformulierung. Diese Ungleichungen definieren in vielen Fällen Facetten und gehören somit zu den theoretisch stärksten Ungleichungen. Zudem entwickeln wir einen Branch-and-Bound Algorithmus auf Basis neuer Formulierungen und struktureller Ergebnisse. In zwei umfassenden Rechenstudien zeigen wir, dass beide Ansätze die Berechnung optimaler robuster Lösungen erleichtern. Insbesondere der Branch-and-Bound Algorithmus übertrifft alle bisherigen Ansätze deutlich. Im zweiten Teil betrachten wir das Problem der Planung des Apothekennotdienstes, welcher eine durchgängige Versorgung mit Arzneimitteln sicherstellt. Das Problem besteht darin, täglich einer Teilmenge der Apotheken 24-Stunden Dienste zuzuweisen, sodass eine angemessene Versorgung gewährleistet und gleichzeitig die Belastung der Apotheken minimiert wird. Wir stellen ein Planungsmodell vor, das in Zusammenarbeit mit der Apothekerkammer Nordrhein entwickelt wurde und zeigen, dass die Berechnung eines zulässigen Plans NP-schwer ist. Wir entwickeln Algorithmen, die dennoch in kurzer Zeit nahezu optimale Pläne für das Gebiet Nordrhein berechnen. Die berechneten Pläne verteilen insgesamt weniger Dienste als der reale Plan der Apothekerkammer Nordrhein, weisen jedoch eine unfaire Konzentration von Diensten auf. Daher diskutieren wir Strategien zur Integration von Fairness in die Planung. Wir zeigen theoretische Resultate zu Fairness in Optimierungsproblemen, auf deren Grundlage wir Notdienstpläne berechnen, die nahezu maximal fair sind.

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.

OpenAccess:
PDF
(zusätzliche Dateien)