title: Algorithm engineering for generic subset optimization problems
Creators: name: Woydt, Henning
Publisher: name: Friedrich-Schiller-Universität Jena
Year: 2024
Subjects: subject: Cardinality-constrained
subject: Branch-and-Bound-Methode
subject: Submodulare Funktion
subject: 510

description: The Cardinality Constrained Maximization problem for submodular monotone set functions arises in many problems like Group Closeness Centrality and k Medoid Clustering. Submodular set functions encode a diminishing return, while monotone set functions never decrease in value. Due to the NP-hard nature of Cardinality Constrained Maximization, most works focus on approximating good solutions. However, exactly solving the problem is required in many fields, like Healthcare Facility Location. As exact algorithms are usually designed for one specific problem, there has not been much research for the general problem. In this work, we design and implement an efficient branch-and-bound algorithm to maximize arbitrary submodular monotone set functions under a cardinality constraint. We assume that we only have access to the set function f via a block-box oracle, which can return the value f(S) for any arbitrary set S. Our algorithm utilizes multiple reduction rules that enable us to prune large parts of the search space. Additionally, we design an efficient branching strategy that traverses the search space in a gradient-like manner, always expanding into the part of the search space that most likely contains a maximizing solution. The cost and accuracy of the branching strategy can be controlled via Lazy Evaluations. To evaluate our developed algorithm, we consider the problems Group Closeness Centrality, Partial Dominating Set, and k-Medoid Clustering. We evaluate which reduction rules prune the search space the best. Additionally, multiple configurations for Lazy Evaluation are compared to each other to determine which configuration saves the most time in practice. Our experiments show that our algorithm is multiple magnitudes faster than the current State-of-the-Art algorithm for Cardinality Constrained Maximization. The overall fastest configuration of our algorithm keeps the required work at each node to a minimum, while still deploying an accurate branching-strategy.
description: Die Maximierung submodularer monotoner Mengenfunktionen unter einer Größenbeschränkung taucht in vielen Problemen wie der optimalen Platzierung von Betriebsstätten oder im Clustering von Datenpunkten auf. Submodulare Funktionen zeigen einen stetig abnehmenden Ertrag, während monotone Mengenfunktionen nie an erreichtem Wert verlieren. Aufgrund der N P-Härte des Problems fokussieren die meisten Arbeiten sich auf das Lösen durch Approximationen. Dennoch ist in vielen Bereichen eine exakte Lösung gewollt, wie zum Beispiel bei der Platzierung von Krankenhäusern und Arzt-Praxen. Weil exakte Algorithmen üblicherweise nur für spezielle Probleme entwickelt wer- den, ist die Forschung für das generelle Problem noch nicht sehr weit. In dieser Arbeit entwerfen und implementieren wir einen effizienten Branch-and-Bound Algorithmus der jegliche submodulare monotone Funktion unter einer Größenbeschränkung maximieren kann. Wir nehmen dafür an, dass wir nur durch eine Black-Box Zugriff auf die Mengenfunktion f haben und diese für jede Menge S den Wert f (S) zurückgeben kann. Unser Algorithmus verwendet mehrere Reduktionsregeln, die es ihm erlauben große Teile des Suchraumes zu entfernen. Zusätzlich gestalten wir die Suche des Algorithmus effizient da er immer in die Richtung des Suchraumes expandiert, in der die beste Lösung er- wartet wird. Die Kosten und Genauigkeit dieser Suche kann durch Lazy Evaluation kontrolliert werden. Um unseren Algorithmus zu evaluieren, nutzen wir die Probleme Group Closeness Centrality, Partial Dominating Set und k-Medoid Clustering. Wir werten aus welche Reduktionsregel den Suchraum am besten beschränkt. Zusätzlich vergleichen wir mehrere Konfigurationen für Lazy Evaluation um zu evaluieren welche in der Praxis am meisten Zeit spart. Unsere Experimente zeigen, dass unser Algorithmus um mehrere Größenordnungen schneller ist, als der aktuelle State-of-the-Art Algorithmus [73] für das größenbeschränkte Maximierung’s Problem. Die schnellste Konfigu- ration unseres Algorithmus hält die nötige Arbeit an jedem Knoten gering, während gleichzeitig eine präzise Suchstrategie benutzt wird.