h1

000986555 001__ 986555
000986555 005__ 20241204153051.0
000986555 0247_ $$2HBZ$$aHT030753382
000986555 0247_ $$2Laufende Nummer$$a43283
000986555 0247_ $$2datacite_doi$$a10.18154/RWTH-2024-05270
000986555 037__ $$aRWTH-2024-05270
000986555 041__ $$aEnglish
000986555 082__ $$a004
000986555 1001_ $$0P:(DE-82)IDM06469$$aGersing, Timo$$b0$$urwth
000986555 245__ $$aAlgorithms for robust combinatorial optimization with budgeted uncertainty and fair planning of the out-of-hours service for pharmacies$$cvorgelegt von Timo Gersing, M.Sc.$$honline
000986555 246_3 $$aAlgorithmen zur robusten kombinatorischen Optimierung mit budgetierter Unsicherheit und zur fairen Planung von Apothekennotdiensten$$yGerman
000986555 260__ $$aAachen$$bRWTH Aachen University$$c2024
000986555 300__ $$a1 Online-Ressource : Illustrationen
000986555 3367_ $$02$$2EndNote$$aThesis
000986555 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000986555 3367_ $$2BibTeX$$aPHDTHESIS
000986555 3367_ $$2DRIVER$$adoctoralThesis
000986555 3367_ $$2DataCite$$aOutput Types/Dissertation
000986555 3367_ $$2ORCID$$aDISSERTATION
000986555 502__ $$aDissertation, RWTH Aachen University, 2024$$bDissertation$$cRWTH Aachen University$$d2024$$gFak01$$o2024-05-17
000986555 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000986555 5203_ $$aPraktische 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.$$lger
000986555 520__ $$aPractical 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.$$leng
000986555 536__ $$0G:(BMBF)BMBF-05M16PAA$$aBMBF 05M16PAA - Verbundprojekt 05M2016 - HealthFaCT: Optimierung der ambulanten medizinischen Versorgung im ländlichen Raum - Teilprojekt 3 (BMBF-05M16PAA)$$cBMBF-05M16PAA$$x0
000986555 588__ $$aDataset connected to Lobid/HBZ
000986555 591__ $$aGermany
000986555 653_7 $$abranch and bound
000986555 653_7 $$afairness
000986555 653_7 $$apharmacies
000986555 653_7 $$apolyhedral combinatorics
000986555 653_7 $$arobust optimization
000986555 653_7 $$ashift planning
000986555 7001_ $$0P:(DE-82)IDM02252$$aBüsing, Christina Maria Katharina$$b1$$eThesis advisor$$urwth
000986555 7001_ $$0P:(DE-82)IDM00097$$aKoster, Arie Marinus$$b2$$eThesis advisor$$urwth
000986555 7001_ $$aPferschy, Ulrich$$b3$$eThesis advisor
000986555 8564_ $$uhttps://publications.rwth-aachen.de/record/986555/files/986555.pdf$$yOpenAccess
000986555 8564_ $$uhttps://publications.rwth-aachen.de/record/986555/files/986555_AV.pdf$$yRestricted
000986555 8564_ $$uhttps://publications.rwth-aachen.de/record/986555/files/986555_source.zip$$yRestricted
000986555 909CO $$ooai:publications.rwth-aachen.de:986555$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
000986555 9141_ $$y2024
000986555 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000986555 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM06469$$aRWTH Aachen$$b0$$kRWTH
000986555 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM02252$$aRWTH Aachen$$b1$$kRWTH
000986555 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00097$$aRWTH Aachen$$b2$$kRWTH
000986555 9201_ $$0I:(DE-82)125620_20210528$$k125620$$lLehr- und Forschungsgebiet Kombinatorische Optimierung$$x0
000986555 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000986555 961__ $$c2024-07-01T10:27:49.969127$$x2024-05-22T19:26:12.371375$$z2024-07-01T10:27:49.969127
000986555 980__ $$aI:(DE-82)120000_20140620
000986555 980__ $$aI:(DE-82)125620_20210528
000986555 980__ $$aUNRESTRICTED
000986555 980__ $$aVDB
000986555 980__ $$aphd
000986555 9801_ $$aFullTexts