Antworte auf:  Wege modellieren von Kingtom2
Forum:  Graphentheorie, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.21, eingetragen 2020-08-11 20:54    [Diesen Beitrag zitieren]

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.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.20, eingetragen 2020-08-11 18:08    [Diesen Beitrag zitieren]

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.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6248
Herkunft: Milchstraße
 Beitrag No.19, eingetragen 2020-08-11 17:02    [Diesen Beitrag zitieren]

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.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.18, eingetragen 2020-08-11 15:57    [Diesen Beitrag zitieren]

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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.17, eingetragen 2020-08-11 15:53    [Diesen Beitrag zitieren]

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


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.16, eingetragen 2020-08-11 15:39    [Diesen Beitrag zitieren]

Also meinst du, dass Kreise automatisch nicht vorkommen werden?


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.15, eingetragen 2020-08-11 15:31    [Diesen Beitrag zitieren]

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.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.14, eingetragen 2020-08-11 14:40    [Diesen Beitrag zitieren]


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?


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.13, eingetragen 2020-08-11 13:51    [Diesen Beitrag zitieren]

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...


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6248
Herkunft: Milchstraße
 Beitrag No.12, eingetragen 2020-08-11 08:57    [Diesen Beitrag zitieren]

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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.11, eingetragen 2020-08-11 01:10    [Diesen Beitrag zitieren]

(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.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6248
Herkunft: Milchstraße
 Beitrag No.10, eingetragen 2020-08-10 23:21    [Diesen Beitrag zitieren]

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


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.9, eingetragen 2020-08-10 12:03    [Diesen Beitrag zitieren]

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.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.8, eingetragen 2020-08-10 11:06    [Diesen Beitrag zitieren]

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!


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.7, eingetragen 2020-08-10 00:59    [Diesen Beitrag zitieren]

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$.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6248
Herkunft: Milchstraße
 Beitrag No.6, eingetragen 2020-08-09 23:22    [Diesen Beitrag zitieren]

Bring doch mal ein Beispiel, wo das auftritt.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.5, eingetragen 2020-08-09 23:02    [Diesen Beitrag zitieren]

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


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6248
Herkunft: Milchstraße
 Beitrag No.4, eingetragen 2020-08-09 20:12    [Diesen Beitrag zitieren]

Hallo Kingtom2,

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


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.3, eingetragen 2020-08-09 18:20    [Diesen Beitrag zitieren]

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


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.2, eingetragen 2020-08-09 18:18    [Diesen Beitrag zitieren]

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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6582
Herkunft: Niedersachsen
 Beitrag No.1, eingetragen 2020-08-09 17:18    [Diesen Beitrag zitieren]

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.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Themenstart: 2020-08-09 16:44    [Diesen Beitrag zitieren]

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?




 
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]