Programmierbeispiel

  • Wie entscheidet man jetzt eigentlich ob man einen Branch abschneidet oder nicht? Ich hab immer die Bedingung wenn obere Schranke größer als globale untere Schranke, dann wird der linke und rechte Branch abgeschnitten. Ist das richtig so? Oder gibts bei linken und rechten Branch unterschiedliche Bedingungen?

  • Also.... wir haben ja das Problem, dass es mehr als nur eine Ressource gibt. Also nicht nur ein Gewicht pro Item sondern mehrere. Zuerst betrachten wir das Problem einfach für jede Ressource einzeln, als gäbe es die anderen nicht. Also wir machen genau das was wir in der Übung im ersten Beispiel auch gemacht haben. So erhalten wir für jede Ressource ein maximales Ergebnis, welches eben die anderen Ressourcen ignoriert.


    Damit können wir schon mal eines sagen: Das kleinste dieser Teilergebnisse ist eine globale Obere Schranke, denn selbst wenn die anderen Ressource nicht da wären und uns einschränken kann das Ergebnis nicht besser werden als der Wert des kleinsten Ergebnisses.


    Wir speichern uns die Werte der Teilergebnisse und speichern auch, welche Items in der jeweiligen optimalen Lösung enthalten waren.


    Full ACK


    Wenn wir nun das Mehrdimensionale Rucksackproblem lösen, verwenden wir ja Branch & Bound. Also schließen wir immer wieder Items aus, die wir auf keinen Fall einpacken. Wenn das geschieht schauen wir, ob das Item in einer der Teilergebnisse für die einzelnen Ressourcen war. Ist dem so, ziehen wir dessen Profit vom Ergebnis der entsprechenden Teillösungen ab. Die kleinste danach verbleibende Teillösung ist dann unser Upper Bound für das aktuelle Unterproblem.


    Ich versteh hier immer noch was nicht :( Nehmen wir mal an Du hast nur zwei Ressourcen, R1 und R2z und Kapazitaeten von jeweils 1000. Es ist theoretisch möglich, dass die Lösung des MKP keine einzige Lösung der EKP von R1 und R2 enthält. Gegen sein dafür die folgenden 150 Items, wobei 50 zu Demonstrationszwecken immer gleich sind:


    Code
    1. Items[150] = {
    2. 1..50 p(100) r1(1) r2(10.000),
    3. 51..100 p(100) r1(500) r2(500),
    4. 100..150 p(100) r1(10.000) r2(1)
    5. }


    Nach R1 ist der maximale EKP Profit = 5.000 @ Cost = 50, aus den Items 1..50. Ähnliches für das EKP aus R2, mit Items 100..150.


    Wenn ich Deinen Algorithmus richtig verstanden habe dann ist nach ausschließen der Items 1..50 (weil R2 10.000 > 1.000) keine Lösung mehr möglich, da von den 5.000 EKP Upper Bound die 5.000 des ausgeschlossenen Items wieder abgezogen wurde. Die neue Upper Bound ist in dem Moment min(0 aus R1, 5.000 aus R2) = 0, und es werden keine Lösungen mehr besucht.


    Die optimale Lösung ist aber klarerweise 2 Items aus 50..100, zum Profit 200 @ Costs R1 = 1.000, R2 = 1.000, die aber somit nicht gefunden werden.


    Ich vermute mal ich hab hier einen Denkfehler drinnen, wenn ihn mir jemand aufzeigen könnte wäre ich sehr dankbar...

  • Hinweis zum obigen Beispiel: Sortierung ist nach Index, nicht nach Effizienz. Der BnB soll immer ein exaktes Ergebnis liefern, unabhängig der Laufzeit.


  • Hinweis zum obigen Beispiel: Sortierung ist nach Index, nicht nach Effizienz. Der BnB soll immer ein exaktes Ergebnis liefern, unabhängig der Laufzeit.


    Ja, du hast insofern recht, als dass in einem derart konstruierten Fall die Berechnung des Upper Bounds in einer Katastrophe endet. Generell müsste man bei jeder Iteration/Rekursion den Bound neu berechnen in dem man die eindimensionalen KPs löst.

    In R1 hast du ja die Items 1-50 plus eines aus 51-100, also Wert 5100 und Gewicht 550. Wenn wir nun alle Items 1-50 ausschliessen sind wir auf Wert 100. Allerdings hätte nun noch ein zweites Item aus 51-100 platz was den Wert wieder auf 200 steigern würde.


    Bei unseren Testfällen scheint mein Verfahren allerdings gut zu funktionieren, auch wenn die Upper Bounds abweichen von dem was sie eigentlich sein sollen. Da wir allerdings eine heuristische Lösung anstreben und kein exaktes Ergebnis ist das eigentlich kein Problem.


    Ich teste mal, was es für Auswirkungen hat, wenn man bei jeder Iteration neu berechnet...


  • Alles klar. ABER: wozu brauchen wird eine globale und eine lokale untere schranke? Wie würdest du dann vergleichen und wann schneidest du dann den Baum ab? Meiner Meinung nach braucht man keine Globale Obere Schranke, wenn man eine lokale berechnet. Und wenn die lokale upperbound < globale LOWERbound => abschneiden.


    Wozu also eine Globale Upperbound berechnen?

  • Weiß wer ob es Richtlinien zur Code-Dokumentation gibt?


    Es wären mir keine bekannt. Mit Doku sieht's halt besser aus und außerdem tut man sich wesentlich leichter beim Abgabegespräch. Es hilft hin und wieder wenn es Diskussionen bezüglich des Codes gibt und lässt den Tutor erahnen, was die eigentliche Intention des Codes war.

  • Bei unseren Testfällen scheint mein Verfahren allerdings gut zu funktionieren, auch wenn die Upper Bounds abweichen von dem was sie eigentlich sein sollen.


    Stimme zu. Dadurch werden in den 30 sec Teile des Baumes enumeriert, die sonst nicht besucht würden (weil der Algo noch in einem anderen Ast festhängt).


    Da wir allerdings eine heuristische Lösung anstreben und kein exaktes Ergebnis ist das eigentlich kein Problem.


    Achtung: das (heuristische) Ergebnis muss nicht exakt sein, es darf die UB aber keinesfalls unterschätzen -- nur überschätzen. Wenn Du einen Ast abschneidest dann musst Du garantieren können, dass keine bessere Lösung im Ast vorhanden war.

  • Alles klar. ABER: wozu brauchen wird eine globale und eine lokale untere schranke? Wie würdest du dann vergleichen und wann schneidest du dann den Baum ab? Meiner Meinung nach braucht man keine Globale Obere Schranke, wenn man eine lokale berechnet. Und wenn die lokale upperbound < globale LOWERbound => abschneiden.


    Wozu also eine Globale Upperbound berechnen?


    Der globale Upper Bound dient nur als Initiallösung für die eigentliche Upper Bound Berechnung im lokalen Baum. Global kann ich ja sagen, dass dieser Upper Bound auf jeden Fall nicht durch die Lösung überschritten werden kann. Wenn ich jetzt in meinen Baum reingehe, ziehe ich ja von diesem Wert immer was ab. Dadurch sinkt der Upper Bound lokal und nähert sich im Optimalfall immer weiter der optimalen Lösung an. Dieser Lokale Bound ist dann auch der Bound der fürs B&B überprüft wird.


  • Wenn wir nun das Mehrdimensionale Rucksackproblem lösen, verwenden wir ja Branch & Bound. Also schließen wir immer wieder Items aus, die wir auf keinen Fall einpacken. Wenn das geschieht schauen wir, ob das Item in einer der Teilergebnisse für die einzelnen Ressourcen war. Ist dem so, ziehen wir dessen Profit vom Ergebnis der entsprechenden Teillösungen ab. Die kleinste danach verbleibende Teillösung ist dann unser Upper Bound für das aktuelle Unterproblem.


    Aber wenn du nun immer wieder Items aus diesen Lösungen entfernst, dann sinkt der Profit aber es wird auch wieder Kapazität frei. Fügst du dann wieder neue Items hinzu und musst du dann nicht bei jedem Item prüfen, ob es nicht schon in der Lösung ist?

  • Der globale Upper Bound dient nur als Initiallösung für die eigentliche Upper Bound Berechnung im lokalen Baum. Global kann ich ja sagen, dass dieser Upper Bound auf jeden Fall nicht durch die Lösung überschritten werden kann. Wenn ich jetzt in meinen Baum reingehe, ziehe ich ja von diesem Wert immer was ab. Dadurch sinkt der Upper Bound lokal und nähert sich im Optimalfall immer weiter der optimalen Lösung an. Dieser Lokale Bound ist dann auch der Bound der fürs B&B überprüft wird.


    jetzt bin ich verwirrt: du sagst du ziehst vom globalen upperbound den profit der verworfenen items ab. Und was war das dann mit den Teillösungen und profit abziehen?


    und btw. : wenn ich das so mache wie du gesagt hast, also für jede resource aus der sortierten liste solange items auffülle, bis die resource voll ist und dann den kleinsten wert (über alle resourcen) nehme, so ist die obere schranke kleiner als meine beste lösung ohne upperbound. :S

  • Das mit der Verwirrung hab ich befürchtet....


    Schritt 1:
    Wir berechnen für jede Ressource das eindimensionale KP, genau in dem Schema, dass wir in Übung 1, Bsp 1 hatten. Dadurch erhalten wir für jede Ressource einen maximalen Profitwert.


    Schritt 2:
    Wir nehmen den kleinsten Wert der einzelnen KP und nehmen diesen als initialen Upper Bound für das mehrdimensionale KP, das wir ja lösen sollen. Die einzelnen Werte der eindimensionalen KP speichern wir uns allerdings, da wir die noch brauchen, ebenso die Items die in diesen Lösungen enthalten waren.


    Schritt 3:
    Wir starten unseren Branch&Bound.
    Wenn wir nach links Branchen ändert sich nichts am Upper Bound.


    Wenn wir nach rechts Branchen verwerfen wir ja immer ein Item.
    Wir erhalten einen neuen Upper Bound, indem wir prüfen, ob das verworfene Item in einer der Teillösungen der eindimensionalen KP war. Wenn ja, ziehen wir es von der dortigen Lösung ab. Der neue Upper Bound ist wieder der kleinste Wert der eindimensionalen KP nach Abzug der verworfenen Items.


    Wie darwin angemerkt hat, ist das nicht 100% korrekt. Eigentlich müssten wir bei jedem Branching Schritt wieder für jede Ressource das eindimensionale KP lösen (nur eben mit den bereits fixierten Items als fix vorgegeben und ohne die bereits verworfenen Items). Dann erhalten wir ebenso wieder einen Upper Bound, der der kleinste Wert dieser Teillösungen ist.

  • Wie darwin angemerkt hat, ist das nicht 100% korrekt. Eigentlich müssten wir bei jedem Branching Schritt wieder für jede Ressource das eindimensionale KP lösen (nur eben mit den bereits fixierten Items als fix vorgegeben und ohne die bereits verworfenen Items). Dann erhalten wir ebenso wieder einen Upper Bound, der der kleinste Wert dieser Teillösungen ist.


    Genau das habe ich so implementiert. Ist nach 42ms fertig und hat bei mir wohl offensichtlich Fehler drin. :shinner: Aber eigentlich ist das auch mMn ein richtiger Weg für eine lokale obere Schranke.:D


    lg, Daniel



    PS: Allerdings fügt das gleich wieder soviel Komplexität zum Code hinzu, dass es jetzt schon relativ schwer wird Fehler zu finden. Ich bin jetzt bei ca. 2650 Zeilen Code (1093 davon Kommentar). Davon entfällt aber gut die Hälfte auf eine eigene Implementierung einer generischen ArrayList inkl. generischem TimSort bzw. QuickSort für primitve Datentypen. Ich war den SecurityManager Leid und habe in einer früheren Version der Lösung viele unterschiedliche Listen sortiert... :turboezreef:

  • Genau das habe ich so implementiert. Ist nach 42ms fertig und hat bei mir wohl offensichtlich Fehler drin. :shinner: Aber eigentlich ist das auch mMn ein richtiger Weg für eine lokale obere Schranke.:D


    lg, Daniel


    nein, bricht bei mir auch beim ersten testcase sofort ab. Es schneidet da anscheinen zu viel weg. hab mit der jetztigen variante 22787, OHNE upperbound hatte ich hingegen 24078;


    @ sirCotare: was bekommst du bei den ersten 4 testcases raus? Mit deiner implementierung in der du die Upperbound nicht jedes Mal ganz neu berechnest?

  • nein, bricht bei mir auch beim ersten testcase sofort ab. Es schneidet da anscheinen zu viel weg. hab mit der jetztigen variante 22787, OHNE upperbound hatte ich hingegen 24078;


    OHNE upper bound:


    .../input/0000: Schwellwert = 21094. Ihr Ergebnis ist OK mit 24078, Zeit: 30s
    .../input/0001: Schwellwert = 54850. Ihr Ergebnis ist OK mit 58027, Zeit: 30s
    .../input/0002: Schwellwert = 115820. Ihr Ergebnis ist OK mit 120036, Zeit: 30s
    .../input/0003: Schwellwert = 110940. Ihr Ergebnis ist OK mit 113849, Zeit: 30s
    .../input/0004: Schwellwert = 20627. Ihr Ergebnis ist OK mit 22597, Zeit: 30s

  • Also, ich habe bei mir einen fehler gefunden.


    Jetzt mit der implementierung wie darwin es angemerkt hat bekomme folgendes:
    0000: 22787 (7ms !!!!) :(
    0001: 58380 (30s) :)
    0002: 120039 (30s) :)
    0003: 115140 (30s) :D
    0004: 22534 ( 4s!!!) :/


    wie man sieht bekomme ich teilweise schlechtere und teilweise bisschen bis zu extrem viel bessere Lösungen