Branch und Bound Verfahren

Sonnenblume_Hagen schrieb:

Hat man da dann die freie Wahl welche Auftragsfolge man dann nimmt?

Zum Vergrößern anklicken....

An dieser Stelle hat man m.E. die freie Wahl. Nimmt man X5 als nächsten Knoten, wird aber spätestens bei Ermittlung der nächsten Bounds mit X3,X1,X5,X2 oder X3,X1,X5,X4 festgestellt, dass die neuen Bounds größer als 26 sind. Hier gilt nun die Verfahrensweise auf S. 47: Abbruch an dieser Stelle und Fortsetzung der Verzweigung mit dem Knoten mit dem nächsten niedrigsten Bound, also mit X4 (S=26).

Vielen Dank URied,
für die schnelle Antwort.

Ich habe die Aufgabe mit beiden Schranken Mal gerechnet und du hast Recht, die Reihenfolge:
X3,X1,X5,X2 liefert 26
ABER
X3,X1,X5,X4 liefert 34.

Somit wäre der Bound von X3,X1,X5,X4 größer als die oberen Bounds. Diese Lösung wäre also unzulässig.

Sonnenblume_Hagen schrieb:

X3,X1,X5,X2 liefert 26

X3,X1,X5,X4 liefert 34.

Zum Vergrößern anklicken....

Hm, ist zwar nicht so wichtig, aber bei mir liefern X3,X1,X5,X2 33 und X3,X1,X5,X4 30. Das muss ich morgen nochmal zur Wiederholung nachrechnen.

PS: Würde X3,X1,X5,X2 tatsächlich 26 liefern, könnte man ja doch hier verzeigen, da die Bedingung auf S. 47 erfüllt ist. Ich schaue es mir morgen nochmal an. Bis dahin.

Das hier war ich noch schuldig geblieben: Es bleibt bei 33 und 30 wie oben geschrieben.

Super, danke dir. Ich muss dann Mal meine Rechnung nochmal anschauen.