Mengenüberdeckungsproblem

Das Mengenüberdeckungsproblem (oft auch Set Cover Problem) ist eine klassische Fragestellung in der Kombinatorik, der theoretischen Informatik und der kombinatorischen Optimierung. Das Mengenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Gegeben sei eine endliche Menge ${\displaystyle U}$ und eine Menge ${\displaystyle {\cal {{S}=\{S_{1},\ldots ,S_{n}\}}}}$, die ${\displaystyle n}$ Teilmengen ${\displaystyle S_{i}}$ von ${\displaystyle U}$ enthält. Gesucht ist nun eine möglichst kleine Teilmenge ${\displaystyle X\subseteq S}$, dessen Elemente die Menge ${\displaystyle U}$ überdecken.

In folgendem Beispiel, welches nebenstehend abgebildet ist, sind ${\displaystyle U=\{1,\ldots ,5\}}$ und ${\displaystyle {\cal {{S}=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}}}$. Die Vereinigung aller Menge aus ${\displaystyle {\cal {S}}}$ ist offensichtlich die Menge ${\displaystyle U}$. Allerdings können alle Elemente aus ${\displaystyle U}$ auch mit den Teilmengen ${\displaystyle \{1,2,3\}}$ und ${\displaystyle \{4,5\}}$ dargestellt werden, welche eine Lösung des Set Cover Problems in diesem Beispiel darstellen.

Im gewichteten Mengenüberdeckungsproblem (Minimum Weight Set Cover Problem) werden jeder Teilmenge ${\displaystyle S_{i}\in {\cal {S}}}$ außerdem Kosten ${\displaystyle c_{i}\in \mathbb {R} }$ zugewiesen und es gilt eine kostenminimale Überdeckung der Menge ${\displaystyle U}$ zu bestimmen. Für ${\displaystyle c_{i}=1}$ entspricht dies dem klassischen Set Cover Problem.

Das gewichtete Mengenüberdeckungsproblem kann als ganzzahliges lineares Optimierungsproblem modelliert werden. Dazu sei ${\displaystyle y_{i}\in \{0,1\}}$ eine binäre Entscheidungsvariable, die angibt, ob die Teilmenge ${\displaystyle S_{i}}$ Teil der optimalen Auswahl ${\displaystyle X}$ ist (${\displaystyle y_{i}=1}$) oder nicht (${\displaystyle y_{i}=0}$). Die zu minimierende Zielfunktion ist die gewichtete Summe aller ausgewählten Teilmengen ${\textstyle \sum _{i=1}^{n}c_{i}y_{i}}$ und die Nebenbedingungen ${\displaystyle \sum _{i:v\in S_{i}}y_{i}\geq 1\ \forall u\in U}$ garantieren, dass jedes Element ${\displaystyle u\in U}$ in mindestens einer ausgewählten Menge ${\displaystyle S_{i}}$ enthalten ist.

• Egon Balas, Manfred W. Padberg: On the Set-Covering Problem. Operations Research, Vol. 20, Nr. 6, 1972