Branch and Bound Algorithmus

[chris23]

Hallo,

aktuell versuche ich einen Branch and Bound Algorithmus in Python zu implementieren. Das heißt ich verzweige einen Baum immer weiter nach dem kleinsten Bound, bis ich unten angekommen bin. Sobald ich dann unten angekommen bin, durchlaufe ich den Baum wieder von unten nach oben, um nach einem geringeren Bound als meine aktuelle Lösung zu suchen.
Mein Hauptproblem liegt aktuell darin, wie ich am besten den Entscheidungsbaum ablaufe und vor allem wie ich die Bounds an den entsprechenden Stellen im Baum speichern kann.

Wäre über Hilfe wirklich sehr dankbar.

[__blackjack__]

@chris23: Die Frage ist zu allgemein. Und auch ein bisschen komisch, denn man speichert da nichts im Baum sondern hat *einen* vorläufigen Ergebniswert, wo man sich immer das ”beste” Ergebnis merkt, und Zweige im Baum nicht weiterverfolgt, sobald man feststellt, dass das Ergebnis auf dem Weg nicht besser werden kann, als das beste was man bisher hatte. Es muss auch gar keinen ”materialisierten” Baum geben. Es reicht der ”gedachte” Baum, den eine rekursive Lösung aufspannt, wenn man alle Lösungsschritte/Aufrufe als Baum aufzeichnen würde.

[chris23]

Hallo, konkret geht es um einen Algorithmus zur Maschinenbelegungsplanung, wobei eine Auftragsreihenfolge ermittelt werden soll. Wenn ich einen Knoten weiter verzweige, wird das Ergebnis ja immer "schlechter", weil ich ja einen weiteren Auftrag einteile. Und ein Ergebnis hab ich ja eigentlich erst auf der untersten Ebene des Baumes. Nur ich brauche ein Knoten nicht weiter zu verzweigen, wenn dessen "Zwischenergebnis" bereits schlechter als meine aktuelle Lösung ist.
Evtl hab ich aber gerade auch einen Denkfehler.

(Wenn ich es schaffe ein Bild hochzuladen, hätte ich auch ein Ablaufdiagramm zu dem Algorithmus)

[__blackjack__]

@chris23: Ja ein Ergebnis hast Du erst auf der untersten Ebene. Du musst aber gar nicht weitergehen wenn Du an einer Ebene angekommen bist wo das Ergebnis ”schlechter” ist, als das bisher beste Ergebnis, also musst Du nicht alle Wege bis zum Ende gehen. Dazu musst Du Dir eben das bisher beste Ergebnis merken und in jedem Schritt mit dem Zwischenergebnis auf dem aktuellen Weg vergleichen. Ist das Zwischenergebnis schlechter, brauchst Du nicht weitergehen. Man startet dann sinnvollerweise mit einem bisher besten Ergebnis von „unendlich“ (oder „minus unendlich“, je nach dem ob grösser „besser“ oder „schlechter“ bedeutet).

Edit: Bild müsstest Du irgendwo hochladen, beispielsweise bei Imgur.com und dann hier die URL zum *Bild* in img-Tags setzen. Wichtig ist es die URL zum Bild zu verwenden, und nicht zu einer Webseite die das Bild enthält.

[chris23]

leider bekomme ich das gerade nicht hin, geht das auch über die URL zu der Seite?
https://imgur.com/a/wUGIYUd

[__blackjack__]

@chris23: Da wird ja ein Algorithmus beschrieben. Stellt sich die Frage aus dem Eingangsbeitrag denn dann überhaupt? Wo genau hängst Du denn bei der Umsetzung von dem Algorithmus?

[chris23]

Genau, dieser Algorithmus soll letztendlich implementiert werden. Es hängt hierbei hauptsächlich am ersten Bild, also wie ich eben diesen Baum durchlaufe und wie ich diese Zwischenlösungen speichern kann, da ich sie ja evtl irgendwann später weiter verzweigen muss.

[__blackjack__]

@chris23: Mir ist das ja alles etwas zu wirr geschrieben, und auch wenn ich mir den ganzen Artikel dazu anschaue, ist mir das zu viel mit denken verbunden. Ausserdem braucht man wohl auch die 1. Referenz auf die sich der Artikel bezieht, denn auf Details daraus verweist der Text ein paar mal bei der Beschreibung. Den sollte man wohl besser zuerst verstanden haben.

Ich habe jetzt zumindest das Ausgangsproblem verstanden. Und bei den Beispielzahlen kann man einfach alle 720 Jobkombinationen durchrechnen um die günstigste zu finden. Das war mit der Rechenleistung von 1966 wohl noch ein Thema für Optimierungen. Selbst den vollen Baum mit allen 1.957 Knoten könnte man locker aufbauen, sogar mit aus heutiger Sicht eher schwacher Hardware.

Wäre wahrscheinlich tatsächlich mein erster Schritt, dass wirklich ”dumm” zu lösen, um später Ergebnisse von der Implementierung des Algorithmus leicht überprüfen zu können.

Für interessierte hier das Problem und ein Beispiel: Man hat eine Anzahl Maschinen und eine Anzahl Jobs. Jeder Job durchläuft alle Maschinen und braucht für jede Maschine individuell viel Zeit. Die Frage ist in welcher Reihenfolge müssen die Jobs laufen, damit möglichst wenig Wartezeit entsteht, also alle Jobs möglichst schnell fertig sind. Beispielmatrix aus dem Artikel:

Code: Alles auswählen

    M1  M2  M3  M4  M5
J1   5   8  20  15   5
J2   6  30   6   7  17
J3  30   4   5   9  10
J4   2   5   3  28   8
J5   3  10   4   1  15
J6   4   1   4   1   4

Wenn man die Jobs in der Reihenfolge abarbeitet wie sie in der Tabelle stehen, ergibt sich folgende Laufzeit (eine Zeile pro Maschine, Ziffer = Zeiteinheit Job, Punkt = Zeiteinheit Leerlauf:

Code: Alles auswählen

11111222222333333333333333333333333333333445556666
.....1111111122222222222222222222222222222233334444455555555556
.............11111111111111111111..........22222233333444.....55556666
.................................111111111111111.2222222333333333444444444444444444444444444456
................................................11111...222222222222222223333333333..........444444445555555555555556666

Sind am Ende 120 Zeiteinheiten bis Maschine M5 mit dem letzten Job fertig ist.

Bestes Ergebnis wäre die Jobreihenfolge 4, 5, 1, 6, 2, 3 mit 97 Zeiteinheiten bis alle Jobs komplett durch sind:

Code: Alles auswählen

44555111116666222222333333333333333333333333333333
..4444455555555551111111162222222222222222222222222222223333
.......444.......5555....111111111111111111116666.......22222233333
..........44444444444444444444444444445......1111111111111116.2222222333333333
......................................44444444555555555555555111116666222222222222222223333333333

[__blackjack__]

Der Rechner für den die das Programm geschrieben hatten über das der Artikel ist: https://en.wikipedia.org/wiki/ICT_1301

[chris23]

Hallo,
erstmal vielen Dank für den interessanten Einblick, vor allem das mit dem Rechner.
Den Ansatz, erstmal "ineffizient" alle Möglichkeiten durchzuprobieren um das optimale Ergebnis zu bekommen finde ich sehr interessant und hab das mal versucht umzusetzen.
Einen Algorithmus, der mir die Zeitdauer in Abhängigkeit von den Daten und einer Reihenfolge berechnet, hab ich hinbekommen.
Jetzt hängt es bei mir etwas daran, wie ich programmieren könnte, dass mir alle möglichen Reihenfolgen durchprobiert werden. Meine erste Idee war, das irgendwie über Schleifen aufzubauen. Allerdings hab ich hier das Problem, dass die Anzahl meiner Aufträge und damit auch die Länge meiner Reihenfolge (die ich am besten in einem 1-dimensionalen Array speichern möchte) nicht fest ist. Hätte jemand einen Ansatz, wie ich das angehen könnte?

[__blackjack__]

@chris23: `itertools.permutations()`.

[nezzcarth]

Bei so alten Papern lohnt es sich, spätere Arbeiten, die diese referenzieren, anzusehen, um ggf. vereinfachte Darstellungen, neuere Versionen oder auch nur eine historische Einschätzung der Arbeit zu bekommen. So, wie ich das verstehe, wurde diese Art von Algorithmus erst wenige Jahre vorher, Anfang der 1960er, erstmals öffentlich beschrieben, danach dürfte sicher noch einiges passiert sein. Bei Google Scholar finde ich 186 Zitate; das ist gut machbar. Besonders interessant sind hier Review/Survey-Artikel.

[__blackjack__]

Ich habe das durchprobieren aller Möglichkeiten mal in BASIC programmiert. Auf einem VIC 20 mit 3 KiB freiem Arbeitsspeicher läuft das in 10m26s durch. Der C64 braucht ein bisschen länger, weil der Prozessor langsamer getaktet ist: 13m21s. Kompiliert man das BASIC-Programm wird es 9× schneller und ist in 1m26s durch.

Code: Alles auswählen

    1 REM@ £PROTOCOL:£FASTFOR:£FASTARRAY:£SHORTIF:£DATATYPE BYTE
    2 REM@ £BYTE I=FAST,J=FAST,T=FAST,JD=FAST,M(,JO(,BO(
    3 REM@ £WORD RN,RC,BT,C,D,JR(:£CONSTANT MC,JC
   10 TI$="000000":MC=5:JC=6:DIM M(MC,JC),JO(JC),JR(JC),BO(JC)
   20 FOR I=1 TO MC:FOR J=1 TO JC:READ M(I,J):NEXT:NEXT
   30 RN=0:BT=1E9:FOR J=1 TO JC:JO(J)=J:NEXT
   40 RC=1:FOR I=1 TO JC:RC=RC*I:NEXT
   50 PRINT"TRYING";RC;"JOB PERMUTATIONS..."
  100 REM SIMULATE RUN
  110 RN=RN+1:PRINT RN;TAB(5);:FOR J=1 TO JC:PRINT CHR$(JO(J)+48);:NEXT
  120 FOR J=1 TO JC:JR(J)=0:NEXT
  130 FOR I=1 TO MC:C=0:FOR J=1 TO JC:JR=JR(J)
  140 IF JR>C THEN D=JR-C:C=JR
  150 JD=M(I,JO(J)):C=C+JD:JR(J)=C:NEXT:NEXT:PRINT:PRINT"{UP}";
  160 IF JR(JC)<BT THEN BT=JR(JC):FOR J=1 TO JC:BO(J)=JO(J):NEXT
  200 REM CALCULATE NEXT JOB ORDER
  210 I=JC-1
  220 IF I>0 AND JO(I)>JO(I+1) THEN I=I-1:GOTO 220
  230 IF I=0 THEN 900:REM FINISHED
  240 J=JC
  250 IF JO(I)>JO(J) THEN J=J-1:GOTO 250
  260 T=JO(I):JO(I)=JO(J):JO(J)=T:I=I+1:J=JC
  270 IF I<J THEN T=JO(I):JO(I)=JO(J):JO(J)=T:I=I+1:J=J-1:GOTO 270
  280 GOTO 100
  900 REM PRINT RESULT
  910 PRINT:PRINT"BEST: ";:FOR J=1 TO JC:PRINT CHR$(BO(J)+48);:NEXT:PRINT BT
  920 PRINT "IN";TI/60;"SECONDS":END
 1000 REM TIMES EACH JOB TAKES AT EACH MACHINE.
 1010 DATA 5,6,30,2,3,4
 1020 DATA 8,30,4,5,10,1
 1030 DATA 20,6,5,3,4,4
 1040 DATA 15,7,9,28,1,1
 1050 DATA 5,17,10,8,15,4

Das liesse sich recht einfach in Assembler schreiben, dann könnte man den BASIC-Compiler wahrscheinlich noch mal unterbieten.