Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Wege modellieren
Druckversion
Druckversion
Autor
Universität/Hochschule J Wege modellieren
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-09


Hallo, vielleicht hat ja jemand trotz der Temperaturen draußen Lust mir zu Helfen.

Es geht um die Modellierung von Wegen.
Die x_ij^pq gibt an ob die Kante (i,j) auf einem (gerichteten) von p nach q liegt. Ursprünglich ist ein umgerichteter Graph gegeben und in E-Schlange wurden die umgerichteten Kanten {i,j} in zwei gerichtete (i,j),(j,i) umgewandelt.

Bei der dritten Bedingung (Siebe Bild) habe ich jetzt das Problem, dass es vorkommen kann, dass x_ik^pq = x_ki^pq erlaubt ist. Wie kriege ich diesen Fall raus?





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-09


Was stört Dich daran?

Je nach Definition von "Weg" ist es ja durchaus zulässig, eine Kante wieder zurückzulaufen: "von Knoten a nach b nach a nach c nach d".

Ehe man solche Wege durch weitere Forderungen "verbietet", kann man sich fragen, ob sie bei der Optimierung nicht sowieso wegfallen, oder durch den verwendeten Algorithmus nicht entstehen können.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-09


Ich benötige immer den kürzesten Weg in meinem Modell. Das ist schwierig zu erklären aber genau das besagte stört bei weiteren nebenbedingungen. Die Knoten des Wegs sollen einfach alle unterschiedlich sein.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-08-09


Bei kommt dann zum Beispiel die Belegung von a nach b und von b nach a vor und das soll so nicht sein



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6158
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-09


Hallo Kingtom2,

sollen die \(x_{ij}^{pq}\) alle aus {0, 1} sein? Falls ja, kann dann \(x_{ij}^{pq}=x_{ji}^{pq}\) überhaupt auftreten?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-08-09


Ja diese sind aus {0,1}
Ich habe mein Modell mit einem solver getestet und leider tritt genau das auf



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6158
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-08-09


Bring doch mal ein Beispiel, wo das auftritt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-08-10


In einem kürzesten Weg (positive Kantenlängen vorausgesetzt) wird der Fall $x_{ij}=x_{ji}=1$ nicht auftreten, weil das nicht minimal wäre.

Aber wenn es Dich unbedingt stört, fordere doch $x_{ij}+x_{ji}\leq 1$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-08-10


Mein Beispiel wäre ein Kreis mit 9 knoten (die Knoten sind der Reihe nach angeordnet)
Dann möchte ich einen Weg von Knoten 5 nach 9 betrachten
Mit den obigen Nebenbedingungen erhalte ich dann x54=x45=x89=x98=1 und das ist ja kein Weg.

Die Bedingung xij + xji <= 1 sollte aber genügen um das hinzukriegen. Danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-08-10


Ah, jetzt verstehe ich erstmal das Problem. Das Beispiel schon im Themenstart hätte sehr geholfen.

Das Problem ist, dass die Knotenbedingungen für Start- und Endknoten zwar gut gedacht, aber ungenügend umgesetzt sind.

Für p muss die Summe der ausgehenden Kanten minus die Summe der eingehenden Kanten +1 ergeben. Für q dann -1.
Für alle anderen Knoten ist diese Differenz gleich 0, wie in der dritten Bedingung schon richtig gefordert.(*)

Damit kann man sich die zusätzlichen Bedingungen dann sparen.

(*) Manche Autoren vermeiden diese drei unterschiedlichen Nebenbedingungstypen, indem sie eine künstliche Kante (q,p) einführen, dort den Fluss +1 verlangen und dann einheitlich fordern können, dass in jedem Knoten soviel hinein geht, wie auch wieder hinaus geht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6158
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-08-10


2020-08-10 11:06 - Kingtom2 in Beitrag No. 8 schreibt:
Mein Beispiel wäre ein Kreis mit 9 knoten (die Knoten sind der Reihe nach angeordnet)
Dann möchte ich einen Weg von Knoten 5 nach 9 betrachten
Mit den obigen Nebenbedingungen erhalte ich dann x54=x45=x89=x98=1 und das ist ja kein Weg.

Die Bedingung xij + xji <= 1 sollte aber genügen um das hinzukriegen.

Ich denke mal, die Bedingung xij + xji <= 1 ist noch nicht ausreichend.

Nimm etwa x12 = x23 = ... = x89 = x91 = 1 und xij = 0 sonst. Dann sind die drei Gleichungen des TS erfüllt und außerdem gilt stets xij + xji <= 1.

Aber hierdurch wird ein Kreis und kein Weg definiert.

2020-08-10 12:03 - Kitaktus in Beitrag No. 9 schreibt:
Für p muss die Summe der ausgehenden Kanten minus die Summe der eingehenden Kanten +1 ergeben. Für q dann -1.
Für alle anderen Knoten ist diese Differenz gleich 0, wie in der dritten Bedingung schon richtig gefordert.

Damit kann man sich die zusätzlichen Bedingungen dann sparen.

Die kann man sich wohl trotzdem nicht sparen

Nimm
x54 = x45 = x56 = x67= x78 = x89 = 1 und xij = 0 sonst



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-08-11


(2020-08-10 23:21 - StrgAltEntf in <a
Nimm
x54 = x45 = x56 = x67= x78 = x89 = 1 und xij = 0 sonst
Was soll damit sein? Das _ist_ ein Weg von 5 nach 9. Das es nicht der _kürzeste_ Weg ist, muss die Optimierung dann herausfinden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6158
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-08-11


2020-08-11 01:10 - Kitaktus in Beitrag No. 11 schreibt:
(2020-08-10 23:21 - StrgAltEntf in <a
Nimm
x54 = x45 = x56 = x67 = x78 = x89 = 1 und xij = 0 sonst
Was soll damit sein? Das _ist_ ein Weg von 5 nach 9. Das es nicht der _kürzeste_ Weg ist, muss die Optimierung dann herausfinden.

Für mich ist ja ein Weg immer injektiv. Aber wenn man auf diese Eigenschaft verzichtet, ist das folgende mit Sicherheit kein Weg.
x23 = x32 = x56 = x67 = x78 = x89 = 1 und xij = 0 sonst

Wenn der Kreis zusätzlich die Sehne {2, 4} enthält, wäre auch
x23 = x34 = x42 = x56 = x67 = x78 = x89 = 1 und xij = 0 sonst
ein Weg von 5 nach 9, sogar ohne doppelt durchlaufende Kante.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-08-11


Na gut, ich gebe mich geschlagen, wenn man Wert darauf legt, dass nur echte Wege zulässige Lösungen sind, dann braucht man weitere Nebenbedingungen.

In der Praxis wird das dann aber ziemlich kompliziert. Wie verindert man denn, dass es neben dem eigentlichen Weg noch irgendwo anders einen geschlossenen Kreis gibt?!
Praktischerweise stellt man solche Nebenbedingungen nicht auf, wenn die Struktur des Problems sicherstellt, dass _optimale_ Lösungen die Bedingungen von sich aus einhalten. Positive Kantenlängen vorausgesetzt, wird kein _kürzester_ Weg einen Knoten mehrfach durchlaufen, oder sonstwie Kreise enthalten.

Bemerkung am Rande: Bei einigen Optimierungsproblemen bietes es sich an, auch wesentliche Nebenbedingungen zunächst wegzulassen und dann iterativ die Nebenbedingungen explizit hinzuzunehmen, die vom aktuell gefundenen Lösungskandidaten nicht erfüllt werden.
Beim Problem des Handlungsreisenden findet man mit einer linearen Relaxation z.B. typicherweise Lösungen, die aus mehreren Einzelkreisen bestehen. Ist A die Knotenmenge eines solchen Kreises, dann nimmt man als zusätzliche Forderung auf, dass es mindestens zwei Kanten im Schnitt von A und V-A geben muss. Damit wird ein Teil des bisher zulässigen Lösungsraums abgeschnitten und man "nähert" sich in der nächsten Iteration der tatsächlichen Lösung.
Siehe Schnittebenenverfahren, Branch-and-Cut-Verfahren...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2020-08-11



Für p muss die Summe der ausgehenden Kanten minus die Summe der eingehenden Kanten +1 ergeben. Für q dann -1.
Für alle anderen Knoten ist diese Differenz gleich 0, wie in der dritten Bedingung schon richtig gefordert

Also benötige ich diese Bedingungen und xij+xji <=1 ? Sehe ich das richtig?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-08-11


Wenn es nur darum geht, auf dem Papier etwas hinzuschreiben, kannst Du sie mit dazu nehmen.
Wenn es darum geht, reale Probleme zu lösen, würde ich es erstmal ohne probieren. Zusätzliche Nebenbedingungen erhöhen tendenziell den Aufwand und zum Finden der optimalen Lösung werden sie nicht benötigt, da schon die Zielfunktion, dass man (positive Kantenlängen vorausgesetzt) nicht unnütz hin und her läuft.
Dein Problem ist entstanden durch fehlerhafte Nebenbedingungen für die Knoten p und q, wie in #9 erläutert.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2020-08-11


Also meinst du, dass Kreise automatisch nicht vorkommen werden?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-08-11


Kann eine Lösung, die einen Kreis positiver Länge enthält optimal sein?
Warum? Warum nicht?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2020-08-11


Ich verstehe was du meinst. Vielleicht habe ich mich da falsch ausgedrückt. Bei meinem Problem ist nicht immer der kürzeste Weg gefordert aber meistens wird er genutzt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6158
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2020-08-11


2020-08-11 15:39 - Kingtom2 in Beitrag No. 16 schreibt:
Also meinst du, dass Kreise automatisch nicht vorkommen werden?

Bei meinem zweiten Beispiel in #12 (das mit der zusätzlichen Sehne) sind die Gleichungen aus dem Themenstart (mit der Korrektur von Kitaktus aus #9: "Für p muss die Summe der ausgehenden Kanten minus die Summe der eingehenden Kanten +1 ergeben. Für q dann -1.") erfüllt. Zusätzlich ist xij + xji <= 1 für alle Kanten {i, j} gegeben. Trotzdem kann ein Kreis entstehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2020-08-11


Ja da hast du recht. Ich sollte mir meine anderen Bedingungen und die Zielfunktion anschauen und überlegen warum immer der kürzeste Weg gewählt wird.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6550
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-08-11


2020-08-11 15:57 - Kingtom2 in Beitrag No. 18 schreibt:
Ich verstehe was du meinst. Vielleicht habe ich mich da falsch ausgedrückt. Bei meinem Problem ist nicht immer der kürzeste Weg gefordert aber meistens wird er genutzt.
Wie in #13 angedeutet ist es schwierig (aber nicht unmöglich) die Existenz von Kreisen durch zusätzliche Nebenbedingungen auszuschließen. Man könnte z.B. für jeden p-q-Schnitt fordern, dass er genau eine Kante enthält. Sind halt $2^{N-2}$ weitere Nebenbedingungen ...

Randbemerkung:
Es gibt einige NP-vollständige Probleme, die sich als lineare Optimierungsprobleme formulieren lassen. Einziger Haken - man benötigt leider exponentiell viel Nebenbedingungen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2 hat die Antworten auf ihre/seine Frage gesehen.
Kingtom2 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]