Branch-and-Bound

Vorgehensweise

Dominanz

Von Dominanz spricht man, wenn für jede Belegung aus einer Teilmenge eine nicht schlechtere zulässigeLösung konstruiert werden kann. Werdennicht alle Optimallösungen gesucht, sondern nur eine, dann erübrigt sich dieSuche in T, selbst wenn die Schranken alleine nicht ausreichen,T von der weiteren Durchmusterung auszuschließen. Dies steigertmitunter die Effizienz des Verfahrens erheblich, beispielsweise im mehrdimensionalen Zuschnittsproblem, obwohl Dominanztests nicht zur ursprünglichen Methode Branch-and-Bound gehören.

Beispiel: bei sei zu lösen. Eine untere Schranke ergibtsich sofort, indem alle Summanden nach unten abgeschätzt werden, also2 - 5 - 5/2 = - 5, 5. Branch-and-Bound ohne Dominanzüberlegungen anzuwenden,erweist sich hier als unnötig aufwändig. Wegen ist x₁ so klein wie möglich zu wählen, einerlei wie großx₂ ist, das heißt x₁ = 2. Für x₂ = 5 wird z = - 3, 4; bei ist z > - 3 und damit nicht optimal. Die einzige Optimallösunglautet x₁ = 2, x₂ = 5.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Branch-and-Bound aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung