Hallo,
ich muss ein LP aufstellen und habe Probleme mit einer Nebenbedingung.
Die Ausgangslage ist ein maximaler Spannbaum. Da ich ein Clustering mit k Clustern und maximalem Gewicht erhalten möchte, will ich k-1 Kanten mit dem kleinsten Gewicht entfernen. Dafür soll ich erstmal ein LP aufstellen.
Mein Ansatz:
$$ min \sum \limits_{(i, j) \notin (E(T)} w_{i,j} * x_{i,j} \\ \sum \limits_{(i, j) \notin (E(T)} x_{i,j} = k-1 $$
Die Zielfunktion soll das Gewicht der Kanten, die nicht mehr im Baum T sind minimieren. Dazu benutze ich den Inzidenzvektor x. Die erste Nebenbedingung stellt sicher, dass genau k-1 Kanten entfernt werden, damit ich k Cluster erhalte. Allerdings brauche ich noch eine zweite Nebenbedingung, die sicherstellt, dass beim Herausnehmen einer Kante, der Baum eine Zusammenhangskomponente mehr erhält, damit die k Cluster sichergestellt sind.
Leider habe ich keine Idee, wie ich das in eine Nebenbedingung packen soll. Vielleicht habe ich auch einen komplett falschen Ansatz, um das Problem zu lösen.
Ich wäre sehr dankbar für jegliche Hilfe! :)
Liebe Grüße
Lisa
