Mengenüberdeckungsproblem

Mathematisches Problem aus dem Gebiet der Kombinatorik

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.

Eine Instanz des Mengenüberdeckungsproblems

Problembeschreibung

Bearbeiten

Gegeben sei eine endliche Menge   und eine Menge  , die   Teilmengen   von   enthält. Gesucht ist nun eine möglichst kleine Teilmenge  , dessen Elemente die Menge   überdecken.

In folgendem Beispiel, welches nebenstehend abgebildet ist, sind   und  . Die Vereinigung aller Menge aus   ist offensichtlich die Menge  . Allerdings können alle Elemente aus   auch mit den Teilmengen   und   dargestellt werden, welche eine Lösung des Set Cover Problems in diesem Beispiel darstellen.

Das gewichtete Mengenüberdeckungsproblem

Bearbeiten

Im gewichteten Mengenüberdeckungsproblem (Minimum Weight Set Cover Problem) werden jeder Teilmenge   außerdem Kosten   zugewiesen und es gilt eine kostenminimale Überdeckung der Menge   zu bestimmen. Für   entspricht dies dem klassischen Set Cover Problem.

Formulierung als Optimierungsproblem

Bearbeiten

Das gewichtete Mengenüberdeckungsproblem kann als ganzzahliges lineares Optimierungsproblem modelliert werden. Dazu sei   eine binäre Entscheidungsvariable, die angibt, ob die Teilmenge   Teil der optimalen Auswahl   ist ( ) oder nicht ( ). Die zu minimierende Zielfunktion ist die gewichtete Summe aller ausgewählten Teilmengen   und die Nebenbedingungen   garantieren, dass jedes Element   in mindestens einer ausgewählten Menge   enthalten ist.

Literatur

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