Im Rahmen des Kolloquiums des Graduiertenkollegs Algorithmic Optimization findet am

Montag, dem 15. Juli 2024
16:00 Uhr c.t.
Hörsaal 9

folgender Vortrag statt:

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

Prof. Dr. Fabio Furini, Sapienza University of Rome

Wir untersuchen eine Familie von diskreten Optimierungsproblemen, bei denen es um die Maximierung des Erwartungswerts einer konkaven, streng steigenden und differenzierbaren Funktion geht, die mit einem Set-Union-Operator zusammengesetzt ist. Der Erwartungswert wird in Bezug auf eine Menge von Koeffizienten berechnet, die Werte aus einer diskreten Menge von Szenarien annehmen. Die Funktion modelliert die Nutzenfunktion des Entscheidungsträgers, während der Set-Union-Operator eine Deckungsbeziehung zwischen zwei Grundmengen, einer Menge von Items und einer Menge von Metaitems, modelliert. Dieses Problem verallgemeinert das von Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149-169, 2011) eingeführte Problem und kann als gemischtes ganzzahliges nichtlineares Programm mit binären Entscheidungsvariablen modelliert werden, die mit den Items und Metaitems verbunden sind. Sein Ziel ist es, eine Teilmenge von Metaitems zu finden, die den Gesamtnutzen für die von ihr abgedeckten Items maximiert. Es findet u.a. Anwendung bei der Suche nach der maximalen Abdeckung und bei Problemen der Maximierung des Einflusses. In diesem Papier schlagen wir eine doppelhypografische Zerlegung vor, die es ermöglicht, die mit den Elementen verbundenen Variablen herauszuprojizieren, indem die strukturellen Eigenschaften der Nutzenfunktion und des Set-Union-Operators getrennt genutzt werden. Dank dieser Methode wird die Nutzenfunktion durch eine exakte äußere Annäherung linearisiert, während der Set-Union-Operator auf zwei Arten linearisiert wird: entweder (i) durch eine Umformulierung, die auf submodularen Schnitten basiert, oder (ii) durch eine Benders-Zerlegung. Wir analysieren aus einer theoretischen Perspektive die Stärke der Ungleichheiten der resultierenden Umformulierungen und betten sie in zwei Branch-and-Cut-Algorithmen ein. Wir zeigen auch, wie unsere Umformulierungen auf den Fall erweitert werden können, in dem die Nutzenfunktion nicht notwendigerweise steigend ist. Anschließend vergleichen wir unsere Algorithmen experimentell mit einer Standardreformulierung, die auf submodularen Schnitten basiert, mit einem hochmodernen globalen Optimierungslöser und mit dem gierigen Algorithmus für die Maximierung einer submodularen Funktion. Die Ergebnisse zeigen, dass die Methode, die auf der Kombination einer äußeren Approximation mit Benders-Schnitten basiert, die anderen Algorithmen deutlich übertrifft.