Branch-and-Bound Verfahren |
| 11.08.2017, 13:19 | uio123 | Auf diesen Beitrag antworten » |
| Branch-and-Bound Verfahren ich hatte letztes Semester eine Vorlesung zur linearen Optimierung. U.a. haben wir auch das Branch&Bound Verfahren zur ganzzahligen linearen Optimierung kurz angerissen. Um die einzelnen Simplexalgorithmen (primales und duales) besser zu verstehen, habe ich diese implementiert. Die Implementationen scheinen richtig zu sein, da ich alle 'einfacheren' Beispiele aus der Vorlesung und die ich im Internet finden konnte, das korrekte Ergebnis liefern. Wie man dann so rumspielt, habe ich dann neue ganzzahlige Beispiele ausgedacht, die eigentlich eine ganzzahlige Lösung haben sollten. Jedoch bricht das Verfahren zwischenzeitlich immer wieder ab. Zunächst waren einige Rundungsfehler im Nachkommastellenbereich das Problem, nach Vergrößerung der linearen Programme, treten jedoch folgende Ergebnisse auf, die ich nicht nachvollziehen kann. - Ein Branch kommt zu dem Entschluss eine bereits erhaltene <= oder >= Bedingung (nicht ganzzahlige Variable) wieder einzufügen in den Branch. Ist dies normal oder kann das nicht sein? - Es kommen <= 0 Bedingungen hinzu. Die <= 0 Bedingungen kann ich noch nachvollziehen, jedoch wird diese dann wie jede andere Bedingung auch in die A-Matrix eingebracht und auch Schlupfvariablen dafür eingefügt? Ich löse zunächst das erste relaxierte Problem mit dem revidierten Simplexverfahren und schwenke nach dem Hinzufügen einer Restriktion auf das duale Verfahren. Muss hier irgendwas beachtet werden? Ich habe die Matrizen und Vektoren der relaxierten primalen Lösung bisher einfach ins duale Verfahren geworfen und die richtige Lösung erhalten. Ich würde auch gerne ein Beispiel zeigen, jedoch entalten die linearen Programm meist über 500 Variabeln und es sind einige 100 Iterationsschritte nötig. Bisher habe ich auch noch kein kürzeres nicht funktionierendes Beispiel finden können. Evtl. kann ich das noch in zusammengefasster Form nachreichen. Hat jemand zu den oben genannten Fragen / Aspekten Ideen? Mir fällt seit einigen Tagen nichts mehr neues ein... Gruß |
||
| 11.08.2017, 18:01 | Elvis | Auf diesen Beitrag antworten » |
Mixed Integer Programming funktioniert in Theorie und Praxis ganz hervorragend, es hat allerdings einige Jahre gedauert, bis stabile und zuverlässige Algorithmen entwickelt wurden, die Branch and Bound Verfahren benutzen. Es ist nicht so einfach, wie es sich in der Theorie darstellt, du brauchst dich also nicht wundern, wenn es nicht auf Anhieb funktioniert, das ist in der Software-Entwicklung normal. Teste deine Modelle mit professioneller Software, dann wirst du zumindest Anhaltspunkte haben, ob deine Software oder deine Modelle für unerwartete Ergebnisse verantwortlich sind. |
||
| 20.08.2017, 15:24 | uio123 | Auf diesen Beitrag antworten » |
Danke für deine Antwort. Es wird mir wohl nichts anderes ausbleiben, als mit anderen Programmen gegen zu testen. Zwei 'einfachere' Fragen hätte ich jedoch noch: 1. Muss beim Wechel von einem primalen Algorithmus zum dualen Algorithmus eine Dualisierung des linearen Programms erfolgen beim Branch-and-Bound Verfahren? 2. In einem Buch bin ich des öfteren über folgende Darstellung gestolpert, über deren Ausdruck ich mir unsicher bin: wobei X eine Matrix ist. Soll dies die inverse transponierte Matrix darstellen. Also ? Gruß |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
