Separierung Blütenungleichung < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:57 Do 14.07.2011 | | Autor: | Stoecki |
Hallo an alle,
Kennt jemand einen Algorithmus zum Separieren von Blütenungleichungen bei einem Matching oder eine Quelle, in der man sowas nachlesen kann? Aus komplexitätstheoretischer Sicht müsste es in polynomieller Zeit möglich sein, die am stärksten verletzte Ungleichung zu berechnen.
Zur Erklärung: Sei G=(V,E) ein Graph und N(v) die Menge aller zu v benachbarten Knoten. Dann ist durch
max [mm] c^T [/mm] x
s.d. [mm] \sum_{w \in N(v)} x_{vw} \leq [/mm] 1 [mm] \forall [/mm] v [mm] \in [/mm] V
[mm] x_{vw} \in [/mm] {0,1}
das gewichtete Matching Problem gegeben. Berechnet man von der zugehörigen linearen Relaxierung das Optimum, ist die Lösung i.A. nicht ganzzahlig. Ziel ist es nun diese fraktionalen Punkte mit Ungleichungen der Form [mm] \sum_{(vw) \in E(U)}x_{vw} \leq [/mm] (|U|-1)/2 für U [mm] \subseteq [/mm] V, |U| ungerade zu separieren.
Ich vermute, dass es mit einem bipartiten Hilfsgraphen gehen muss, bei dem jeder Knoten von G in jeweils eine der Partitionen gesetzt wird und dann ein kürzester Wege Algorithmus darauf angesetzt wird.
Schon mal danke vorab für eure Antworten
Gruß Bernhard
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:15 Mo 18.07.2011 | | Autor: | Stoecki |
Ich habe mir nun folgende LP-Formulierung überlegt:
G=(V,E) ein Graph, und x eine fraktionale Lösung einer Relaxierung des gewichteten Matching Problems
[mm] max_{y,z} \summe_{(v,w) \in E} y_{(v,w)} x_{(v,w)} [/mm] - [mm] \bruch{|S|-1}{2|S|}\summe_{v \in V}z_v
[/mm]
s.d
für alle e=(v,w) gilt:
[mm] y_{(v,w)} [/mm] - [mm] z_{v} \le [/mm] 0
[mm] y_{(v,w)} [/mm] - [mm] z_{w} \le [/mm] 0
und
[mm] \summe_{v \in V} z_{v} [/mm] = |S|
wobei S [mm] \subseteq [/mm] V mit |S| ungerade
[mm] y_{(v,w)}, z_{v} \in [/mm] {0,1}
Die Nebenbedingungen sagen foldendes aus:
[mm] y_{(v,w)} [/mm] - [mm] z_{v} \le [/mm] 0
[mm] y_{(v,w)} [/mm] - [mm] z_{w} \le [/mm] 0
Eine Variable [mm] y_{(v,w)} [/mm] darf nur dann 1 sein, wenn beide Knoten v,w in der Menge S sind.
[mm] \summe_{v \in V} z_{v} [/mm] = |S|
Die Menge S soll genau |S| Knoten enthalten.
[mm] y_{(v,w)}, z_{v} \in [/mm] {0,1}
Die Variablen müssen binär sein. (Ein Knoten ist drin oder nicht. Er ist zur Hälfte drin geht also nicht)
Folgendes problem bei dieser Formulierung. Die Bedingung [mm] \summe_{v \in V} z_{v} [/mm] = |S| sorgt dafür, dass das Problem nicht mehr total unimodular ist, wodurch das Restriktionspolytop fraktionale Ecken hat. Die Frage die nun noch bleibt ist, ob bei dieser Zielfunktion, wenn ich dieses IP für alle |S| = 3,5,7,...,k [mm] \le [/mm] |V| löse ohne die Ganzzahligkeit explizit zu betrachten immer eine Lösung generiert, die dennoch ganzzahlig ist (für ein |S|).
Ich habe mir folgende Gedanken bereits gemacht. Der Simplex-Algorithmus wird dazu tendieren, möglichst wenig Variablen z in die Basis aufzunehmen, da die mit negativen Koeffizienten in die Basis eingehen. Andersrum wird der Algorithmus versuchen möglichst viele y Variablen in die Basis zu zwingen. Hier werden jedoch gleichermaßen die Knotenvariablen z in die Basis gezwungen. Die Frage ist also, ob bei diesem Ansatz es optimal ist, die Knotenvariablen anteilsmäßig einzubeziehen oder komplett. Ich tendiere dazu, dass es wohl anteilsmäßig sein wird, was bedeutet, dass dieser Ansatz so nicht funktioniert. Eventuell ließe er sich dann jedoch retten, wenn man die fraktionalen Punkte hier schnell separiert bekommt und doch noch mittels Branch and Cut innerhalb weniger Iterationen auf was Ganzzahliges kommt. Ein Grund warum ich glaube, dass die Knotenvariablen Anteilsmäßig eingehen, ist dass es 2|E| viele basisspalten gibt, jedoch nur |E|+ |V| viele Variablen, die nicht zum Slack (zu den Schlupfvariablen) gehören. Hat jemand dazu vielleicht eine Idee?
Gruß Bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Do 21.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
