Algorithmus Branch&Bound S. 34

Tach zusammen,

ich hab grad die ÜA 2.4 von Seite 37 (Ganzzahlige Optimierung) gerechnet und bin auf eine Stelle im Algorithmus fürs B&B-Verfahren gestoßen, die meines erachtens nicht ganz korrekt ist:

Schritt 5: Zur Berechnung des z(r+1) soll man die obere bzw. untere Grenze vom z(r) abziehen.

Im vorhergehenden Beispiel 2.3 wurde aber nicht der tatsächliche Wert der Grenzen abgezogen, sondern lediglich der Absolutwert:
Grenze U = -21/4 und Grenze O = -1/4, von z = 45/4 abgezogen ergäbe das z > 45/4, im Text darunter heißt es aber "ZFW höchstens 6 [45/4 - 21/4) ... höchstens 11 [45/4 - 1/4]". Hier wurde also der Absolutwert abgezogen.

Ebenso wurde es so in der ÜA 2.4 gemacht, zumindest für das P1 laut Lösung.

Ist das ein Fehler in dem Algorithmus? Wenn ja, was ist die richtige Formel? Wenn nein, was mach ich falsch? 😕

Danke und Grüße aus München,

Toni

Dem Algorithmus geht es gut. Du kannst nicht lesen. 🙂

Bei Ü2.4 steht, daß nur x1 ganzzahlig ist.
Beim Beispiel 2.3 geht es darum, bei welcher Variable man es zu erst mit dem Einführen der ganzzahligkeit versuchen sollte.
Zwei unterschiedliche Fragestellungen, zwei unterschiedliche Wege.

Und Du weißt nicht zufällig, wie man einen Rucksack rekursiv packt?

Unabhängig von der Fragestellung wird doch in beiden benannten Rechnungen der Schritt "alter ZFW - U(i) bzw. - O(i)" vollzogen, bei dem Beispiel lediglich verbal, in der ÜA muss man ihn zum Füttern des Verzweigungsbaums machen.

Und in beiden Aufgaben wurde entgegen des Algorithmus, der ja u.a. aus dem vorhergehenden Beispiel heraus "entwickelt" wurde und den man zum Lösen von ÜA 2.4 anwenden soll, nicht der jweilige tatsächliche negative Wert der Grenzen abgezogen, sondern entweder der Absolutwert abgezogen oder der tatsächliche Wert hinzuaddiert. Aber auf keinen Fall wurde der tatsächliche Wert - wie im Algorithmus vorgegeben - subtrahiert.

Gut, bei dem Beispiel lass ich mit mir reden 😉 , da man nicht mit Sicherheit sagen kann, dass damit der Schritt 5 des Algorithmus vollzogen werden soll. Aber in der ÜA... ???

Wo liegen die Schwierigkeiten beim Rekursiven Rucksack?

Hm, also ich verstehe Dein Problem nicht. In der Übungsaufgabe gibt es nur eine Variabel zur Auswahl, warum willst Du dort noch Punkt 5 machen? Also der Rechner würde das sicher machen, aber Du bist doch ein Mensch?

In Punkt 5 geht es um die Auswahl der nächsten Verzweigung: vergleiche bei allen ganzzahligen Bedingungen, die nicht ganzzahlig sind, die obere und untere Schranke, als nächstes nimmt man entweder die obere oder untere Schranke als Auswahlparameter.

So, der Mensch an sich sieht aber, daß I nur aus der Menge x3 besteht, also ist es auch vertane Liebesmüh irgendwelche Schranken zu berechnen, nur um festzustellen, daß sowohl Obere als auch Untere Schranke bei x3 im Vergleich zu allen andneren {} größer ist.

Das ist aber auch nicht wirklich klausurrelevant. dort müssen wir nicht wirklich viel B&B machen und die Wahl des aufzubrechnenden Knotens ist auch (so gut wie) vorgegeben.

Na und beim Rucksack habe ich einfach keine Ahnung was er will, ich verstehe kein Rödderisch und finde das auch nirgendwo anders beschrieben.
Könntest Du mir nicht mal einen kleinen Rucksack basteln? So einen kleinen feinen mit 2-3 Variablen? Das ist bestimmt ganz leicht, aber irgendwie habe ich da ein Brett vor dem Kopf.

Ja, dass x2 die einzige zu verzweigende Variable ist, das weiß man auch ohne die Schrankenberechnung. Nichtsdestotrotz braucht man laut Algorithmus die Schranken zur Berechnung der beiden neuen Zielfunktionswerte - und genau da liegt mein Problem. Die Formel laut Algorithmus lässt dort die beiden negativen Schranken abziehen, was ja den/die Zielfunktionswert/e effektiv erhöht. Richtig bzw. mathematisch korrekt wäre es aber, den Absolutwert der Schranken abzuziehen bzw. den tatsächlichen Wert zu addieren.
Da fällt mir gleich noch was auf: müsste nicht das P1 der Lösung das eigentlich P2 sein (also nur die Nummerierung der beiden Probleme) - wieder nur dem Algorithmus folgend: P1 (das P2 der Lösung) ist das Problem, dessen ZFW sich aus der Subtraktion der O(i) ergibt (die hier maßgeblich ist - sie bestimmt die (ja: einzige) Pivotzeile), P2 wird laut Algorithmus gar nicht in die Liste L aufgenommen und somit auch nicht untersucht - höchstens noch für die Konstruktion des Baumes "ermittelt").

Oder soll man direkt zu Beginn von 5. beim Vergleich der beiden Grenzen deren Absolutwerte vergleichen? Dann ist natürlich zuerst U(i) zu untersuchen, weil größer. Dann wäre es auch logisch, dass man links das P1 als Dead-End erhält und erst als zweites dann die schlußendlich Lösung untersucht und freudig feststellt, dass hier alles passt...

Naja, ich versuch mich mal noch an ÜA 2.5 - mal schaun, ob ich dort mit dem Algorithmus den kompletten Baum richtig konstruieren kann.

Vielleicht kannst du ja mal ausführlichst deine Schritte bei ÜA 2.4 posten, wen du sie mit dem Algorithmus löst...

Und zu deinem Rucksack-Dingens... wo ist genau das Problem? Ich vermute mal, das Herleiten dieser feinen, auf den allerersten Blick absolut aussagekräftigen Tabellen und das Ermitteln der Lösung bereitet Schwierigkeiten, oder? Das ist eine schöne Hin- und Herrechnerei... kommt aber so vermutlich auch nicht dran

Hm, ich glaube, Du machst Dir da zu viel Gedanken zu.
Ich bin so gemein, daß ich mir das in der KE bis gestern auch nicht wirklich angesehen habe, sondern den B&B wie in PET angewendet habe. Und das macht der Lehrstuhl auch. 🙂

Es ist auch, zumindest bei Simplex B&B, wenn man mehrere ganzahlige Variablen hat, ziemlich gleich, welche Variable man einschränkt, es müssen im Nachhinein eh alle ganzzahlig sein. Und die Reiheinfolge, also ob z.B x2>=2 vor x2<=3 gerechnet wird. Tja, da gehe ich, wie auch der Lehrstuhl, immer gleich vor. Nach links geht der <= Zweig, nach rechts der <= Zweig. Und gerechet wird wie man liest, von links nach rechts. Und ja, da könnte man vorher noch per Schrankenbestimmung abschätzen, welcher Zweig der bessere sein könnte, nur ist es schneller kurz den Simplex zu erweitern. Bzw. bei den hier meist verwendeten Rucksackabwandlungen, die Lösung per rhythmischem Hinsehen zu sehen.

Mal als Beispiel Aufgabe 3 Klausur März 09, da habe ich wenigstens die Musterlösung von der EA dazu und weiß, daß der Lehrstuhl wie ich vorgeht.

max 4x1+3x2+5x3+8x4
unN
3x1+2x3+4x3+5x4<=19

b)
Lösen des Relaxierten Problems:
Rendite:
a1=4/3
a2=3/2
a3=5/4
a4=8/5

a4>a2>a1>a3

Ohne Ganzzahligkeit einlasten nach Rendite:
P0:
x4=19/5=3,8
Z=3,8*8=30,4

So jetzt wird gebrochen, und das ohne Schrankengedöns, nach links mit x4<=3 und nach rechts mit x4>=4

P1:
x4<=3
s.o. Einlasten unter der neuen Nebenbedingung --> x4=3 Engpassrest=19-5*3=4
Danach einlasten vom zweitbesten Gut:
x2=4/2=2
Z=2*3+8*3=30

Ganzahligkeit erreicht. Da die Lösung auch ganzahlig sein muß und die Lösung <1 vom Optimum abweicht, ist dies auch eine optimale Lösung.
Brechen nach P2 ist daher nicht nötig, aber so G-tt will:

P2
x4>=4
keine Lösung

Dafür benötigt man weder Simplex, noch Schranken.

Den könnte man bei Aufgabe 2 09.08 anwenden, aber selbst dort macht er keine Schrankenberechnung, sondern bricht fröhlich mal nach x1 dann nach x2 und in der Durchnummerierung weiterhin mit erst nach unten, dann nach oben brechen
Und auch dort läßt sich die Aufgabe ohne Simplex schneller lösen, und den kann er auch nicht komplett erwarten, denn dann müßte man auch die Knoten ohne Lösung per Simplex angehen.

Und ja, beim Rucksackdings verstehe ich weder, wie er die Tabelle bastelt, noch wie ich da etwas ablesen kann. Und doch, das kam schon einmal dran, nämlich in der letzten Klausur Aufgabe 3. Daher büdde büdde, bastel mir das doch kurz vor.

ich hätte auch Interesse an der Bastelei mit dem Rucksack rekursiv 😉 büdde, büdde
es kam schon mehrmals dran, auch in den Diplomklausuren.

So Freunde, ich hab mir mal die Mühe gemacht, ich hoffe es ist verständlich... ich bin lediglich stur dem Algorithmus gefolgt, aber das dauert seine Zeit. Vielleicht gehts mit ein wenig Übung schneller, ansonsten siehts für die Klausur echt mies aus.

Also hier das Beispiel 4.1 ausführlichst... Falls es Anmerkungen oder gar Korrekturen gibt, bitte gebt mir Bescheid - dann muss ich mein Weltbild - zumindest bezüglich rekursivem Rucksackpacken - kippen 😉

So denne, ich geh dann mal pennen. Bis Morgen,

Toni

Danke, hat ein wenig *klickk* gemacht. Ich kann zwar immer noch das Ergebnis nur mit rhythmischem Hinsehen erraten, aber zumindest kann ich die Tabelle hoffentlich in der Klausur zusammenbasteln.

Ich habe Probleme mit Schritt 9.) und 10.): Was bedeutet "Andernfalls sei P1 das letzte Problem der Liste. Streiche dieses Problem in L und gehe zu Schritt 10"? Was mache ich nun wenn ich in der Liste vor Schritt 9 (P2, P3, P4) stehen habe? Ist in Schritt 10 immer r1 mit dem neuen z zu vergleichen? Wie kann z1 kleiner sein als das neue z? z1 wird doch noch ganz am Anfang berechnet und ist damit immer größer als die z nachfolgender Probleme