Exakte Suche erklärt
Exakte Suche liefert nicht nur eine gute, sondern eine bewiesen beste Lösung, im Unterschied zu Heuristiken, die schnell gute Lösungen suchen, ohne Optimalität zu garantieren (bei großen Instanzen kann der Beweis allerdings am Zeitlimit scheitern). In der Logistik zum Beispiel: welche Auswahl an Paketen maximiert den Gesamtwert, ohne das Gewichtslimit eines Lieferwagens zu überschreiten, oder wie viele Rollen braucht ein Zuschnittauftrag mindestens?
Zwölf Stücke in zwei Linien mit demselben methodischen Bogen: erst das Rucksackproblem, dann Cutting Stock, das Problem, für das Column Generation und Branch & Price erst richtig gebraucht werden. Die Stücke sind großenteils keine gleichberechtigten Alternativen, sondern Bausteine auf dem Weg zu einer praktischen Kombination.
In short: Covers exact methods for combinatorial optimization: branch and bound, dynamic programming, cutting planes, constraint programming, column generation and branch and price. Interactive demos follow two problems, knapsack and cutting stock.
Hintergrund zum Thema: Packen und Zuschnitt.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Branch and Bound verständlich erklärt
Wie eine Schranke ganze Äste eines riesigen Suchbaums streicht und so beweist, dass nichts Besseres mehr kommt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Befunden.
Rucksack: Branch & Bound als Wurzel
Anders als bei der Clustering-Linie sind die fünf Stücke hier größtenteils keine gleichberechtigten Alternativen, sondern Bausteine auf dem Weg zu einer praktischen Kombination: deshalb bewusst nur ein einfacher Abhängigkeitsgraph, keine Auswahlfrage. Branch & Bound ist die Wurzel. Dynamische Programmierung ist ein Kontrast, kein Fix: derselbe Rucksack, aber Tabellierung statt Suchbaum, mit einer eigenen, andersartigen Schwäche. Schnittebenen schärft dieselbe LP-Schranke, ganz ohne zu verzweigen, und läuft zusammen mit Branch & Bound in Branch & Cut zusammen, der ersten Konvergenz dieser Linie und dem, was reale Solver tatsächlich einsetzen. Constraint Programming schließlich ist ein unabhängiger Zweig: Constraint-Propagation statt Schranken-Vergleich, für Nebenbedingungen, die eine Rucksack-LP-Schranke gar nicht ausdrücken kann. Eine zweite Linie mit demselben methodischen Bogen, aber einem anderen Vehikel-Problem (Cutting Stock, bis zu Column Generation und Branch & Price) folgt im nächsten Abschnitt.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
Verwandt in anderen Linien
- Multi-Agenten-Koordination — Die Multi-Agenten-Linie nutzt beides: Ihre exakte Referenz ist ein CP-SAT-Löser (Constraint Programming), und DPOP in der DCOP-Demo ist verteilte dynamische Programmierung mit exponentiell wachsenden Tabellen. Die Auktion stellt Teilmengen-DP gegen CP-SAT (CP-SAT scheitert dort schon bei n = 11 bis 12).
- Netzwerkfluss — Die Netzwerkfluss-Linie setzt zwei Werkzeuge dieser Linie auf Netzen ein: die Pfad-Formulierung erzeugt wie die Column-Generation-Demo Spalten (dort Zuschnittmuster, hier Pfade), und die Cut-Set-Ungleichungen im Fixkosten-Netzdesign sind Schnittebenen wie in der Cutting-Planes-Demo.
- Lineare Programmierung — Die LP-Schranke, die Schnittebenen und Branch & Bound bei jedem Knoten neu berechnen, liefert ein Simplex-Verfahren: die Linie Lineare Programmierung baut den Tableau-Simplex und den dualen Simplex von Grund auf, der nach einem Schnitt oder einer Verzweigungsschranke von der alten Basis weiterrechnet.
- Adversarische Suche — Die Alpha-Beta-Demo dort wendet dasselbe Schranken-Prinzip wie Branch & Bound hier an, nur auf ein Nullsummenspiel mit einem Gegenspieler statt auf einen einzelnen Entscheidungsträger: obere und untere Schranken beschneiden Teilbäume, deren Wert das Endergebnis nachweislich nicht mehr ändern kann.
- Ranking — Die exakte Kemeny-Aggregation der Rangaggregation ist eine Teilmengen-Rekursion, dasselbe Muster wie am Rucksack, hier für eine lineare Ordnung.
- Härte und Struktur — Die Schranke macht den Suchbaum klein: Branch & Bound am Rucksack lebt von seiner Schranke, die Größte-Clique-Demo der Linie Härte und Struktur ersetzt sie durch eine Färbung und zeigt live, wie viele Knoten das spart und wo die Färbung mehr kostet, als sie bringt.
- Komplexitätsklassen — Die Tabelle der dynamischen Programmierung hängt am Wert der Gewichte; Zahlen und Härte macht die Länge der Zahlen zum Regler und zeigt, was das Runden der Werte spart.
Branch & Bound am Rucksackproblem
Verfolgen Sie den Suchbaum von Branch & Bound Schritt für Schritt: bei wenigen Paketen passt er komplett aufs Bild, bei mehr Paketen entscheidet Pruning über Hunderte statt Zehntausende Knoten. Ein Umschalter zwischen starker und schwacher Bound und ein Regler für die Wert/Gewicht-Korrelation zeigen live, wovon Pruning-Erfolg abhängt: die starke Schranke bleibt auch bei hoher Korrelation wirksam, die schwache nicht.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Dynamische Programmierung am Rucksackproblem
Verfolgen Sie, wie die DP-Tabelle Zeile für Zeile gefüllt wird und ein Rückverfolgungspfad danach die optimale Auswahl aufdeckt: keine Verzweigung, keine Schranke, nur Tabellierung. Ein Regler für die Größenordnung der Gewichte zeigt live, wo dieselbe Tabellierung an eine Grenze stößt, die Branch & Bound gar nicht kennt.
Demo starten →Schnittebenen am Rucksackproblem
Sehen Sie, wie eine gefundene Deckung die LP-Schranke Runde für Runde verschärft, ganz ohne einen Suchbaum zu verzweigen. Ein Vergleich mit dem wahren Optimum zeigt live, dass Schnitte allein oft nicht bis zum Beweis reichen, der Ausgangspunkt für Branch & Cut.
Demo starten →Branch & Cut am Rucksackproblem
Verfolgen Sie, wie Wurzel-Schnitte aus der Schnittebenen-Demo den Suchbaum von Branch & Bound schon vor der ersten Verzweigung schärfen. Ein Drei-Wege-Vergleich zeigt live, wie viele Knoten die Kombination gegenüber jedem Verfahren allein einspart.
Demo starten →Constraint Programming am Rucksackproblem
Sehen Sie Constraint-Propagation Paket für Paket ausschließen, sobald ein inkompatibler Partner gewählt wird, ganz ohne LP-Schranke. Ein Vergleich mit klassischem Branch & Bound und dem echten OR-Tools-CP-SAT-Solver zeigt live, wie viele aussichtslose Äste die Propagation von vornherein vermeidet.
Demo starten →Cutting Stock: von Branch & Bound bis Branch & Price
Sieben Stücke auf einem zweiten Vehikel für exakte Suche, mit demselben methodischen Bogen wie die Rucksack-Linie davor: eine Rolle fester Breite, mehrere Auftragsbreiten mit Bedarf, gesucht die minimale Anzahl Rollen. Über die Brücke „Bedarf zu Einzelstücken aufgelöst“ wird daraus Bin Packing. Der Anlass für diese zweite Linie: Column Generation und Branch & Price brauchen ein Problem mit natürlich exponentiell vielen impliziten Variablen (Mustern). Das gibt reines Rucksack nicht her.
Nicht zu verwechseln mit der bereits bestehenden Fall-Demo Cutting Stock (Column Generation vs. First-Fit-Decreasing-Heuristik, mehrere Rollentypen): diese Linie vergleicht Verfahren gegen Verfahren auf einem bewusst einfacheren, einzigen Rollentyp, nicht Verfahren gegen Heuristik.
Wie bei der Rucksack-Linie ein einfacher Abhängigkeitsgraph statt einer Auswahlfrage, hier allerdings mit ZWEI Konvergenzpunkten statt einem. Branch & Bound ist die Wurzel, bewusst ohne Symmetrie-Mitigation. Dynamische Programmierung ist ein Kontrast: derselbe Bedarfsvektor als Zustand statt Suchbaum, mit einer völlig anderen eigenen Schwäche (der Zustandsraum wächst mit der Anzahl Auftragstypen, nicht mit der Kapazität). Der Symmetrie-Schnitt behebt tatsächlich, was die Wurzel nur zeigte, und läuft mit ihr in Branch & Cut zusammen, echtes, per-Knoten wiederholtes Branch & Cut, realistischer als die erste Linie. Constraint Programming ist ein unabhängiger Zweig mit einer echten Materialsorten-Nebenbedingung statt künstlicher Zufalls-Paare. Column Generation schließlich ist der eigentliche Anlass dieser Linie, ein grundlegend anderer Lösungsansatz (LP + Spaltengenerierung statt Suche), und läuft mit der Wurzel in Branch & Price zusammen: echte Ryan-Foster-Verzweigung schließt, was Column Generation offen ließ.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
Branch & Bound am Cutting-Stock-Problem
Verfolgen Sie, wie aus Bedarfsmengen Einzelstücke werden und ein Suchbaum sie auf möglichst wenige Rollen verteilt. Ein Vergleich mit einer Suche, die gleich gefüllte Rollen zu einem Ast zusammenfasst, zeigt live, wie stark austauschbare Rollen den Suchbaum aufblähen können: im Beispiel-Preset rund das 11-fache, bei einer typischen Zufallsinstanz aber nur etwa das 1,09-fache (Median). Bewusst unbehoben, der Ausgangspunkt für den nächsten Schnitt.
Demo starten →Dynamische Programmierung am Cutting-Stock-Problem
Verfolgen Sie, wie eine Rekursion über Bedarfsvektoren Rolle für Rolle einen Schnittplan aufbaut: keine Verzweigung, nur Memoisierung. Ein Balkendiagramm zeigt live, dass der Zustandsraum hier mit der Anzahl Auftragstypen explodiert, komplett unabhängig von der Rollenbreite: der genaue Gegensatz zur ersten (Rucksack-)Linie.
Demo starten →Symmetrie-Schnitte am Cutting-Stock-Problem
Sehen Sie, wie ein echter algorithmischer Schnitt baugleiche offene Bins gar nicht erst als eigene Äste erzeugt, statt Symmetrie nur zu diagnostizieren. Ein Vorher/Nachher-Vergleich auf derselben Instanz zeigt live eine Reduktion um mehr als das 40-fache.
Demo starten →Branch & Cut am Cutting-Stock-Problem
Verfolgen Sie, wie eine an jedem Suchbaum-Knoten frisch gelöste LP-Schranke mit dem Symmetrie-Schnitt zusammenwirkt: echtes, per-Knoten wiederholtes Branch & Cut statt einmalig eingefrorener Schnitte. Ein Dreier-Vergleich zeigt live, was jede Zutat einzeln beiträgt.
Demo starten →Constraint Programming am Cutting-Stock-Problem
Sehen Sie Constraint-Propagation kapazitätspassende, aber materialinkompatible Bins ausschließen, bevor sie überhaupt entstehen: eine echte, aus der Praxis stammende Nebenbedingung statt künstlicher Zufalls-Paare. Der echte OR-Tools-CP-SAT-Solver bestätigt live jedes Ergebnis.
Demo starten →Column Generation am Cutting-Stock-Problem
Verfolgen Sie, wie ein Master-LP gezielt neue Schnittmuster anfordert, statt vorab exponentiell viele durchzuprobieren. Ein Schranken-Vergleich zeigt live eine dramatisch engere Schranke als die einfache Summenschranke, aber auch ehrlich, dass naives Aufrunden allein noch keine gute Lösung garantiert.
Demo starten →Branch & Price am Cutting-Stock-Problem
Sehen Sie, wie echte Ryan-Foster-Verzweigung, nicht naive Verzweigung auf einer Muster-Variable, bei jeder fraktionalen Lösung gezielt zwei Stücke zusammen oder getrennt erzwingt, kombiniert mit Spaltengenerierung an jedem Knoten. Ein Vergleich zeigt live, wie das die Lücke schließt, die naives Aufrunden offen ließ.
Demo starten →Welches Verfahren passt zu meinem Problem?
Ein Entscheidungsbaum über beide Linien: Er fragt nach der Struktur des Problems, nicht nach dem Verfahren. Viele Verfahren gibt es als Demo am Rucksack- und am Cutting-Stock-Problem; der Baum verlinkt die Rucksack-Fassung, nur Column Generation und Branch & Price gibt es allein am Cutting-Stock-Problem.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Schnittebenen allein erreichen den bewiesenen Optimalwert nur in einer Minderheit der Fälle, deshalb führt der Weg über Branch & Cut. Column Generation liefert eine enge Untergrenze (aufgerundet traf sie in über 270 getesteten Fällen immer den Optimalwert), die gerundete Lösung selbst aber nur in rund der Hälfte der Fälle (~48 %); dafür braucht es Branch & Price. Die Dynamische Programmierung wächst beim Rucksack mit der Kapazität, beim Cutting Stock (in dieser Formulierung) exponentiell mit der Zahl der Auftragstypen.
Weitere Linien in diesem Bereich
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.