SAT und Constraint Programming: vom Konfliktlernen bis zur Verfahrenswahl erklärt
Stellen Sie sich vor: Ein Lager hat drei Rampen und viele Aufträge, von denen manche Paare nicht auf derselben Rampe stehen dürfen, weil sie sich nicht vertragen. Der Planer probiert eine Zuordnung, läuft in eine Sackgasse, geht einen Schritt zurück und probiert weiter. Nach einer Weile macht er in einem anderen Ast denselben Fehler noch einmal. Wie kann ein Programm sich merken, warum eine Sackgasse eine war, und wann bringt ein anderer Blick auf die Aufgabe mehr als jedes Merken?
Das ist ein SAT-Problem: Aus Ja/Nein-Entscheidungen und Bedingungen in der Form „mindestens eine dieser Aussagen gilt“ (Klauseln) soll eine Belegung gefunden werden, die alle Klauseln zugleich erfüllt. Ein Löser, der aus jeder Sackgasse eine neue Klausel lernt, betreibt Konfliktlernen. Beim Constraint Programming bleiben Bedingungen wie „alle verschieden“ oder „nicht gleichzeitig“ als Ganzes erhalten, und jede schließt selbst Werte aus (ein Propagator), noch bevor die Suche verzweigt. Die Leitfrage dieser Linie lautet: Was muss ein Löser über die Struktur der Aufgabe wissen, und wann hilft das Lernen, wann ein Mengenargument, wann eine Suche ganz ohne Gedächtnis?
Sechzehn Stücke gehen dem nach. Die erste Gruppe baut den lernenden Löser auf: aus Fehlschlägen lernen, die Buchführung beschleunigen, die nächste Variable wählen, neu beginnen und vergessen. Die zweite fragt, was man damit sonst anfangen kann: Antworten beweisen, Formeln vorher verkleinern, Zählbedingungen und vertauschbare Rampen in Klauseln fassen und möglichst wenige Bedingungen verletzen. Die dritte geht über Mengen-, Maschinen- und Kapazitätsschlüsse und verbindet beides, indem ein Schluss zur Klausel wird. Zum Schluss stehen der Vergleich mit einer lokalen Suche und die Frage, welche Modellwelt zu welcher Aufgabe passt.
Was diese Linie ist und was nicht: Es sind lesbare Python-Löser mit gewählten Annahmen an erzeugten Formeln und Plänen, keine Wettbewerbslöser und keine Aussage über echte Fälle. Gemessen wird in Konflikten, Knoten und Lesezugriffen, nie in Sekunden. Mehrere Erwartungen halten nicht: Das Lernen schlägt die Suche ohne Gedächtnis bei Zufallsformeln erst ab etwa 90 Variablen, eine kleinere Formel braucht nicht weniger Konflikte, und bei großen Zufallsformeln gewinnt die lokale Suche. Die Linie zeigt nicht, dass ein Verfahren das beste ist, sondern woran die Wahl hängt.
In short: Interactive demos on SAT solving and constraint programming: how a solver learns from dead ends, proves its answers and prunes the search with propagators. They also set learning against local search and compare clauses, constraints and mixed-integer models.
Hintergrund zum Thema: Schichtplanung · Lagerlogistik.
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
Konfliktlernen verständlich erklärt
Wie ein Rechenprogramm aus einer Sackgasse eine Regel lernt und warum das erst bei größeren Aufgaben weniger Fehlschläge kostet, bei kleinen Aufgaben und beim Schubfach aber nicht: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Symmetrie brechen bei SAT verständlich erklärt
Warum ein Rechenprogramm dieselbe Sackgasse bei gleichen Rampen immer wieder sucht, wie eine zusätzliche Regel das streicht und warum sie bei leichten Aufgaben nicht sicher hilft: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Lokale Suche gegen Lernen verständlich erklärt
Warum man einen Plan so lange umstellen kann, bis keine Regel mehr verletzt ist, und damit bei zufälligen Aufgaben mit wachsender Größe gewinnt, bei Aufgaben mit Aufbau aber verliert und nicht „geht nicht“ sagen kann: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die 16 Stücke im Überblick
Der Graph zeigt, wie die sechzehn Stücke zusammenhängen. Die Wurzel des ersten Strangs ist Konfliktklauseln lernen; sie setzt auf der SAT-Demo der Komplexitätsklassen auf, deren Suche ohne Gedächtnis dieselbe Sackgasse wiederholt. Aus dem Lernen folgen Verbesserungen: Watched Literals gegen den Aufwand der Propagation, die Variablenwahl nach Aktivität gegen die feste Reihenfolge (mit den Neustarts als Folgestück), das Löschen gegen die Klauselflut und die Kodierung von Zählbedingungen, aus der die Symmetriebrechung und MaxSAT folgen. Im Kontrast stehen das Beweisprotokoll (die Antwort belegen statt finden) und die Vorverarbeitung (kleiner machen vor der Suche). Die Graphfärbung färbt denselben Konfliktgraphen wie die Rampen, fragt aber nach der Reihenfolge des Färbens.
Der zweite Strang beginnt bei AllDifferent und bei Disjunktiv und Edge-Finding. AllDifferent setzt auf der Constraint-Programming-Demo am Rucksack auf, die kein „alle verschieden“ kennt, und übernimmt die Idee des Matchings aus der Hopcroft–Karp-Demo. Die Maschinenschlüsse stehen im Kontrast zur Job-Shop-Demo, die Kapazität größer 1 im Kontrast zur RCPSP-Demo mit ihren Prioritätsregeln. Beide Stränge fließen in Lazy Clause Generation zusammen, einem Propagator, der seine Schlüsse als Klauseln erklärt. Die lokale Suche steht im Kontrast zum Konfliktlernen und übernimmt die Idee „Verschlechterung erlaubt“ aus dem Simulated Annealing. Die Verfahrenswahl am Schluss ist der Zusammenfluss.
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)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Durchgezogene Pfeile beheben eine Schwäche des Vorgängers, gepunktete übernehmen nur eine Idee, gestrichelte Doppelpfeile sind ein Kontrast (derselbe Zweck, andere Bauweise). Graue gestrichelte Knoten sind Bausteine aus anderen Linien, der Doppelrahmen markiert die Verfahrenswahl, in der mehrere Stränge zusammenlaufen. Die Stücke lassen sich in beliebiger Reihenfolge lesen.
Verwandt in anderen Linien
- Komplexitätsklassen — Die SAT-Demo der Komplexitätsklassen zeigt die Suche ohne Gedächtnis (DPLL) und den Phasenübergang und baut das Klausellernen ausdrücklich nicht. Das Konfliktlernen setzt dort an und misst, wann ein Löser aus den wiederholten Sackgassen etwas gewinnt.
- Exakte Suche — Die Constraint-Programming-Demo propagiert Bedingungen am Rucksack und kennt weder „alle verschieden“ noch Mengenargumente. AllDifferent setzt dort an und zählt, was ein Mengenargument sieht, das paarweise Ungleichheit nicht sieht.
- Graphen und Netzwerke — Die Demo Graphfärbung färbt denselben Konfliktgraphen wie die Rampen dieser Linie, fragt aber nach der Reihenfolge des Färbens (Greedy, DSATUR, exakt). Das Konfliktlernen fragt dagegen, welchen Löser man auf die Färbung als Klauselmenge ansetzt.
- Klassische Scheduling-Theorie — Die Job-Shop-Demo und die RCPSP-Demo lösen dasselbe Modell mit Heuristiken und Prioritätsregeln. Disjunktiv und Edge-Finding und Kumulativ blicken in die Propagation im Inneren und zählen die Suchknoten bis zum bewiesenen Optimum.
- Matching-Algorithmen — Die Hopcroft–Karp-Demo findet ein größtes Matching in einem zweiseitigen Graphen. Das Matching nach Régin in AllDifferent ordnet Variablen Werte zu und erkennt daran, wenn mehr Dinge auf weniger Werte nicht passen.
- Trajektorien-Metaheuristiken — Das Simulated Annealing ändert eine Lösung in kleinen Schritten und lässt Verschlechterungen zu, dort an einer Route. Die lokale Suche für SAT dreht in kleinen Schritten einzelne Variablen um und tritt gegen das Konfliktlernen an.
Konfliktklauseln lernen: aus jedem Fehlschlag eine Regel
Verfolgen Sie, wie ein Löser für Ja/Nein-Aufgaben aus jeder Sackgasse eine neue Regel (Klausel) lernt und bis zur Ursache zurückspringt, statt denselben Fehler in anderen Ästen zu wiederholen. Bei Zufallsformeln mit 110 Variablen und 4,26 Klauseln je Variable braucht die Suche ohne Gedächtnis das 3,53-Fache an Widersprüchen. Der Haken: Bis etwa 70 Variablen gibt es keinen Vorsprung, und beim Schubfach bleibt er bis sieben Löcher aus.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Watched Literals: gleiche Antwort, weniger Klauseln anfassen
Sehen Sie, wie der Löser je Klausel nur zwei Literale beobachtet, statt bei jeder Belegung alle Klauseln ganz zu lesen. Die Antwort bleibt gleich, die Lesezugriffe sinken um den Faktor 4,0 bei Zufallsformeln mit 100 Variablen und um den Faktor 47,1 beim Schubfach mit sieben Löchern. Der Haken: Ein Teil davon kommt von anderen Suchwegen, und in 2 von 10 Zufallsformeln liest die Technik sogar mehr.
Demo starten →Variablenwahl nach Aktivität statt fester Reihenfolge
Sehen Sie, wie der Löser zuerst die Variable wählt, die zuletzt oft an Konflikten beteiligt war, statt nach fester Nummer. Bei Zufallsformeln mit 150 Variablen erreicht die feste Reihenfolge bei 8 von 12 Formeln das Budget von 20 000 Konflikten, die Aktivität bei keiner. Der Haken: Beim Schubfach in der Taube-für-Taube-Nummerierung gewinnt die feste Reihenfolge, und der beste Zerfallswert der Aktivität wechselt mit der Formelmenge.
Demo starten →Neustarts: dieselbe Aufgabe, andere Reihenfolge
Verfolgen Sie, wie der Löser nach einer festen Folge (Luby) alle Entscheidungen verwirft und neu beginnt, die gelernten Klauseln aber behält. Bei Färbungen von Aufträgen auf drei Rampen braucht er mit Neustarts in allen 10 Aufgaben weniger Konflikte, im Median 0,42 der Konflikte ohne. Der Haken: Bei Zufallsformeln hilft es nur in 5 von 12 Aufgaben, in 7 ist es neutral.
Demo starten →Klauseln löschen: Gedächtnis kostet Zugriffe
Sehen Sie, was es bringt, die am wenigsten nützlichen gelernten Klauseln immer wieder zu löschen. Bei Zufallsformeln mit 175 Variablen sinkt der Bestand beim Löschen alle 500 Konflikte um 85 %, die Zahl der Lesezugriffe um 54 %. Der Haken: Die Zahl der Konflikte sinkt dadurch nicht, und bei zu häufigem Löschen steigt sie sogar über die Streubreite der Läufe ohne Löschen.
Demo starten →Beweise schreiben und prüfen: „unerfüllbar“ glauben, weil ein zweites Programm nachrechnet
Verfolgen Sie, wie der Löser zu jedem Konflikt eine Zeile in ein Protokoll schreibt und ein zweites, einfaches Programm jede Zeile nachrechnet, bevor man „unerfüllbar“ glaubt. Bei unerfüllbaren Zufallsformeln mit 30 bis 50 Variablen steht je Konflikt genau eine Zeile, und der Prüfer akzeptiert alle 60 Protokolle. Der Haken: Das Format belegt keine Schritte mit neuen Variablen, und beim Schubfach wächst das Protokoll je Loch mindestens um das Vierfache.
Demo starten →Vorverarbeitung: kleiner heißt nicht weniger Konflikte
Sehen Sie, wie sich eine Formel vor der Suche verkleinern lässt (Einheiten, Subsumption, Elimination) und ob die Suche dadurch leichter wird. Bei Zählbedingungen an Knotenüberdeckungen sinkt die Variablenzahl des Sinz-Zählers von 1 476 auf 425,2 und die Zahl der Propagationen um 56,6 %. Der Haken: Die Konflikte sinken in keiner der sieben Messzeilen erkennbar, in fünf steigt ihr Median sogar.
Demo starten →Kardinalität kodieren: dieselbe Zählregel in wenigen oder sehr vielen Klauseln
Sehen Sie, wie sich „höchstens k von n“ als Klauseln aufschreiben lässt: Für 25 Variablen und k = 5 braucht die einfache Kodierung 177 100 Klauseln, der Sinz-Zähler 259, bei gleicher Antwort. Der Haken: Der Totalizer, eine dritte Kodierung, braucht am Optimum ab 50 Variablen im Median weniger Konflikte als der Sinz-Zähler, knapp darunter ist kein Unterschied erkennbar.
Demo starten →Symmetrie brechen: aus 27 932 Konflikten wird einer
Sehen Sie, wie eine zusätzliche Regel (eine Farbe erst, wenn die vorige vorkam) vertauschbare Rampen, Farben oder Löcher auseinanderhält: Beim Schubfach mit acht Löchern sinken die Konflikte von 27 932 auf einen. Der Haken: Bei einer leichten Schur-Aufgabe (Zahlen auf vier Mengen verteilen) steigt ein Standardlauf von 6 auf 352 Konflikte; über 20 Zufalls-Seeds ist das nicht belegt.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →MaxSAT: Kerne statt Zähler, und die Kerngröße geht mit den Unterschieden einher
Verfolgen Sie, wie ein MaxSAT-Löser, der möglichst wenige weiche Bedingungen verletzen lässt, Kerne sucht: kleine Gruppen von Bedingungen, die zusammen nicht erfüllbar sind. Bei Kernen aus zwei Literalen und 50 Kontrollpunkten braucht das Verfahren OLL im Median 1 Konflikt, die lineare Suche 1 839,5. Der Haken: Bei großen Kernen liegt OLL nur beim Faktor 1,3 bis 1,4 vor der linearen Suche, und die Kernminimierung macht die Gesamtkosten meist größer.
Demo starten →AllDifferent: das Mengenargument
Sehen Sie, was ein Mengenargument erkennt, das paarweise Ungleichheit nicht erkennt: Sieben Dinge passen nicht auf sechs Werte, die paarweise Suche braucht dafür 1 237 Knoten, das Mengenargument einen. Am Rotationsplan bricht die paarweise Suche in 42 von 380 Läufen am Budget ab, das Matching nach Régin in keinem. Der Haken: In 5 von 19 Zellen kostet Régin im Median mehr Grundoperationen als die paarweise Suche.
Demo starten →Disjunktiv und Edge-Finding: Schlüsse über Maschinen
Verfolgen Sie, wie am Job Shop ein Paar-Test und das Edge-Finding schon vor dem Verzweigen Reihenfolgen ausschließen. Der Paar-Test macht den Sprung: bei sechs Aufträgen auf sechs Maschinen im Median das 12,3-Fache weniger Knoten. Edge-Finding bringt im Median nur 9 % weniger Knoten, im Tail deutlich mehr. Der Haken: Eine schnellere Datenstruktur (Θ-Λ-Baum) ändert die Knotenzahl in keiner von 40 Instanzen.
Demo starten →Kumulativ: Pflichtteile statt Paare
Sehen Sie, wie bei einer Ressource, die mehrere Aktivitäten zugleich bedienen kann, das Zeitprofil der Pflichtteile die Fenster der anderen verkleinert (Timetabling). Bei zehn Aktivitäten sinkt der Median der Knoten bis zum bewiesenen Optimum von 5 354 auf 452. Der Haken: Bei 15 und 20 Aktivitäten liegt der Median am Budget, und die Energieprüfung bringt in dieser einfachen Fassung kaum etwas.
Demo starten →Lazy Clause Generation: ein Propagator erklärt seinen Schluss
Sehen Sie, was das Klausellernen am Job Shop bringt, wenn sonst alles gleich bleibt: Bei acht Aufträgen auf acht Maschinen sinkt der Median der Konflikte von 4 085,5 auf 353,5, ohne Lernen bricht die Hälfte der Läufe am Budget ab. Der Haken: Eine auf das Problem zugeschnittene Suche braucht in 4 von 5 Größen weniger Zähleinheiten, und das Schubfach ist ein Sonderfall.
Demo starten →Lokale Suche gegen CDCL: kein Gedächtnis, keine Beweise
Sehen Sie, wie eine Suche ohne Gedächtnis (eine Variable einer verletzten Klausel umdrehen) gegen den lernenden Löser antritt. Bei Zufallsformeln mit 300 Variablen und 4,0 Klauseln je Variable braucht sie im Median 33-mal weniger Lesezugriffe, über die gelösten Fälle. Der Haken: Auf Aufträgen auf Rampen kehrt es sich um, ebenso bei Zufallsformeln mit 100 Variablen und 4,26 Klauseln je Variable, und nur das Lernen kann „unerfüllbar“ sagen.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Verfahrenswahl: SAT, CP oder MIP, gemessen woran?
Sehen Sie, wie sich dieselbe Aufgabe als Klauseln, als Constraint-Modell und als gemischt-ganzzahliges Programm lösen lässt: Am Rotationsplan bis Ordnung 22 sind alle drei Welten leicht: das MIP löst alle 160 Instanzen, 159 davon in höchstens einem Knoten. Am Job Shop wächst es mit Big-M dagegen schnell (2 290 Knoten im Median bei acht mal acht). Der Haken: Es sind zwei Aufgabenfamilien und kleine Stichproben bei großen Größen, keine Rangliste.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Stellen Sie sich vor, eine Planungsaufgabe soll von einem Löser entschieden werden, und Sie fragen sich, welches Werkzeug dafür passt. Der Baum fragt zuerst nach der Form der Bedingungen und erst danach nach dem Ziel: Sind es Ja/Nein-Variablen mit Klauseln, müssen Dinge verschieden sein, dürfen sich Aufgaben nicht überlappen? Danach geht es um Zufall oder Struktur, vertauschbare Teile, Zählbedingungen und die Stelle, an der der Löser hakt.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Mehrere Fragen können zugleich zutreffen; der Baum ordnet nach Frage, nicht nach Rangfolge. Alle Antworten beruhen auf den Messungen der Stücke, nicht auf einer Diagnose Ihrer Aufgabe: Sie gelten für die gemessenen Familien (Zufallsformeln, Färbung von Konfliktgraphen, Rotationspläne, Job Shops) und für lesbare Python-Löser. Bei Zufallsformeln mit 100 Variablen und 4,2 bis 4,26 Klauseln je Variable liegt das Lernen vor der lokalen Suche, bei größeren dahinter.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
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.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
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.
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.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
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.
Packen: Reihenfolge und Platzierungsregel
Wie packt man Pakete, Rechtecke und Quader in wenige Behälter, und wie nah am Besten liegt eine einfache Regel? Vierzehn Stücke von der Sortierung bis zur Verfahrenswahl.
Umstauen: Untergrenze und Suche
Wie viele Container müssen mindestens umgestapelt werden, und wann lohnt sich die Suche nach dem Besten? Fünfzehn Stücke von der einfachen Regel bis zur Verfahrenswahl.
Tourenbildung: eine Reihenfolge, optimal zerlegt
Wie bildet man Touren aus einer einzigen Reihenfolge aller Kunden, und wann schlagen Savings, Sweep oder Suche sie? Fünfzehn Demos von der Aufzählung bis zur Verfahrenswahl.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.
Takt und Periodizität
Ein Fahrplan, der sich jede Stunde wiederholt: vier Stücke von den Zeitabständen über die Wartezeit der Umsteiger und die Kreisgleichungen bis zum Betriebstag.