Branch & Bound - Kriterien für Schranken

[grassi3000]

Hi, ich versuch mich grad, nachdem ich da nicht in der VO war, über das Branch & Bound schlau zu machen.

Im Skriptum ist das Verfahren zwar wunderschön anhand des Beispieles erklärt, jedoch kann man anhand dieses nicht wirklich herausfinden, was die genauen Kriterien für die einzelnen Schranken im allgemeinen Fall sind.

Alleine der SatzZunächst berechnen wir z.B. mit einer Heuristik eine zulässige (...) Startlösung mit Wert U und eine untere Schranke L für alle möglichen Lösungswerte(...)Der Satz wird nicht wirklich erklärt, und wirft mehr Fragen auf, als er löst.
Was ist die Startlösung? Was ist die Untere Schranke i.A. Fall

DannAnsonsten wird die Lösungsmenge partitioniert ... Nach welchen Kriterien geschieht dies?

[locutus]

ob es sich um obere oder untere schranken handelt ist abhängig davon, ob es sich um ein maximierungs oder minimierungsproblem handelt.

unabhängig davon ist jede zulässige lösung eine globale schranke (die optimale lösung kann nur gleich gut oder besser aber nicht schlechter sein)

aus den teilproblemen ergeben sich jeweils lokale schranken (besser kann es unter den lokalen bedingungen nicht werden)

die partitionierung erfolgt je nach problemstellung durch aufteilen in (meistens 2) teilprobleme:
rucksack: gegenstand nehmen oder nicht
graph: kante nehmen oder nicht
linear programming: variable <= oder >