Aus N Kandidatenobjekten, jedes mit einem Wert und einem Gewicht, eine Teilmenge so auswählen, dass das Gesamtgewicht eine Kapazität (Budget, Arbeitsstunden, Maschinenstunden) nicht überschreitet und der Gesamtwert maximal ist. In der Literatur das Knapsack-Problem — der Urahn diskreter Auswahlprobleme.
Kurz gesagt
Kommt Ihnen das bekannt vor?
- Ein jährliches Investitionskomitee mit 50-200 Kandidatenprojekten und einem fixen Gesamtbudget von 50-500M TRY — die Reihenfolge der Projekte wird intuitiv und politisch festgelegt; eine 'NPV/Investitionsquote'-Tabelle entsteht, das mathematische Optimum wird aber nicht garantiert.
- Für jeden Kandidaten liegen NPV-Schätzung, erforderliche Investition, erforderliche Arbeitsstunden und erforderliche Maschinenstunden vor (drei Restriktionsdimensionen) — wir haben aber nie ein Auswahlmodell gebaut, das alle gleichzeitig berücksichtigt.
- In der Budgetplanung wird 'von oben nach unten gepickt' — aber kleine, hoch-rentable Projekte, die die letzten 5-10% des Budgets ausfüllen würden, scheitern oft.
- Auswahl digitaler Marketingkampagnen: 30-80 Vorschläge, festes Monats- oder Quartalsbudget; welche Teilmenge maximiert Reichweite/Conversion?
- Zwischen den Kandidaten gibt es Abhängigkeiten (Projekt A senkt Projekt B's Kosten, wenn beide gewählt; Projekt C und D sind sich ausschließend) — das klassische Knapsack-Modell erfasst das nicht und braucht zusätzliche Restriktionen.
- Logistik: ein kapazitätsbeschränktes Cargo-Flugzeug oder Container — jedes Paket hat Wert und Gewicht; maximiere Gesamtwert unter der Kapazität.
- Fondsmanager Small Cap: ein Universum von 200-500 Aktien, fixer Fondsumfang, je Aktie erwartete Rendite und Mindesthandelsgröße; welche Teilmenge?
- Lieferantenvertrag: 100+ Kandidaten, festes jährliches Einkaufsbudget; jede Quelle hat Mindest- und Höchstauftragsvolumen; welche Teilmenge maximiert den Gesamtwert?
Warum es wichtig ist
Wie wird es gelöst?
Technische Tiefe
Wie wird es gelöst?
Technische TiefeIn einem Satz: Sortiere Kandidaten nach Wert pro Gewichtseinheit als Greedy-Start; für die exakte Antwort starte dynamische Programmierung (Kapazität unter 10K) oder MIP (vor allem bei mehrdimensionalen Restriktionen oder Abhängigkeiten) — die beste Teilmenge ergibt sich in Minuten.
In der Operations-Research-Literatur (Disziplin, die Mathematik und Computer für Geschäftsentscheidungen einsetzt) und der Informatik-Literatur ist das das Rucksackproblem (Knapsack Problem) — N Kandidatenobjekte mit Wert (vᵢ) und Gewicht (wᵢ); Kapazität W; welche Teilmenge maximiert Σvᵢ unter Σwᵢ ≤ W? Ein seit den 1950ern erforschtes klassisches Problem, mit Industriestandard-Lösungen über dynamische Programmierung, Branch-and-Bound und moderne MIP-Solver. Lösung in drei Stufen:
1. Modellierung — Variantenwahl und Dateninputs. Die Problemfamilie ist breit; die Anwendung bestimmt die Variante:
- 0/1-Knapsack (binär): jedes Objekt wird gewählt oder nicht, keine Duplikate. Klassische Investitionsprojektauswahl. xᵢ ∈ {0, 1}.
- Bounded Knapsack: beschränkte Anzahl Kopien je Objekt (xᵢ ∈ {0, 1, …, cᵢ}). Lieferantenlots.
- Unbounded Knapsack: beliebige Anzahl je Objekt (xᵢ ≥ 0 ganzzahlig). Kapazitätsbeschränktes Produktionslinien-Bin-Packing oder ganzzahlige Aktienlot-Größen.
- Multi-Dimensional Knapsack (MKP): m Restriktionen; jedes Objekt hat Gewichte in m Dimensionen (Budget + Arbeitsstunden + Maschinenstunden + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ für alle j. Wesentlich schwerer.
- Quadratic Knapsack (QKP): quadratische Zielfunktion — Σᵢvᵢxᵢ + ΣᵢΣⱼpᵢⱼxᵢxⱼ; Wechselwirkungen zwischen Objekten (Synergie).
- Multiple-Choice Multi-Dimensional Knapsack: Objekte in Gruppen; aus jeder Gruppe genau ein Objekt.
- Subset-Sum: Zielwert gleich Gewicht; Gesamtgewicht möglichst nah an Kapazität.
- Knapsack mit Set-Up: das Auswählen eines Objekts verursacht fixe Set-up-Kosten (Gruppen). Produktionslinien, Werkseröffnungen.
Inputs: Kandidatenliste N, Wert- und Gewichtsschätzungen (NPV und Investition; im Marketing geschätzter Conversion-Wert und Kampagnenkosten), Kapazität W (Jahres- oder Monatsbudget, Cargo-Nutzlast), mehrdimensionale Restriktionen (Arbeitsstunden, Maschinenstunden, Kategorie-Sub-Budgets), Abhängigkeitsstruktur (Vorrang, Ausschluss, Kapazitätsrabatt).
2. Lösung — Algorithmik.
- Greedy + LP-Relaxierung: einfachster Ansatz — Objekte nach Wert/Gewicht-Quote sortieren und von oben füllen. Garantiert kein Optimum (klassisches Gegenbeispiel: Kapazität 10, drei Objekte (v,w) = (6,5), (5,4), (4,3) — Greedy 6+5=11, Optimum 5+4+3=12); LP-Relaxierung liefert die Obergrenze für Branch-and-Bound. Praktisch als One-Shot-Check.
- Dynamische Programmierung (DP): der klassische pseudo-polynomielle Algorithmus (Zeit hängt vom numerischen Wert der Kapazität W ab). State dp[i][w] = maximaler Wert mit den ersten i Objekten unter Gewicht w. Übergang dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). Komplexität O(N×W). N = 1000, W = 100.000 TRY-Einheiten = 10⁸ Operationen — auf moderner Hardware Sekunden. Praktische Realität: moderate Instanzen (N ≤ 1000, W ≤ 10⁶) löst DP in Minuten zum Optimum; die ‘NP-hart, also unlösbar’-Intuition ist falsch.
- Branch-and-Bound (Baumsuche mit Beschneidung unaussichtsreicher Zweige): mit LP-Relaxierung als Obergrenze. Eine Kernvariablentechnik ist praktischer State of the Art für Millionen-Objekt-0/1-Knapsack.
- MIP (Mixed-Integer Linear Programming — Optimierung mit teils 0/1-, teils stetigen Variablen): natürliches Werkzeug für mehrdimensionale (MKP) und abhängigkeitsreiche Instanzen. Open-Source- oder kommerzielle MIP-Solver lösen 100-1000-Objekt-MKPs in Minuten bis Stunden zum Optimum (oder mit kleinem Gap).
- FPTAS (Fully Polynomial-Time Approximation Scheme — für jedes ε > 0 eine (1-ε)-Approximation in Polynomialzeit): mit ε = 0.01 garantiert 99% des Optimums.
- Metaheuristik (genetisch, Tabu, Simulated Annealing): für sehr große mehrdimensionale MKP oder abhängigkeitsreiche Instanzen; keine Optimalitätsgarantie, aber praktische Qualität.
Investitionsprojektauswahl (50-200 Objekte, 1 Budget oder 2-4 Restriktionen): MIP oder 0/1-DP liefert das Optimum in Sekunden. Sehr großes MKP (500+ Objekte, 5+ Restriktionen): MIP nahe Optimum oder FPTAS. MIP genügt in den meisten Unternehmensszenarien; spezielle Knapsack-Algorithmen sind selten notwendig.
3. Feldintegration und Sensitivitätsanalyse. Output: gewählte Teilmenge, Gesamtwert, Restriktionsauslastung, LP-relaxierungsbasierte Sensitivität (welches Projekt knapp drin, welches knapp draußen). Investitionskomitee-Bericht: Auswahlempfehlung, alternative Szenarien (welches Projekt ändert sich bei Budget ±10%, welches kommt bei gelockerter Arbeitsstundenrestriktion), explizite Berichterstattung von Abhängigkeits- und politischen Restriktionen. Quartalsweise Neuplanung: neue Vorschläge ergänzen, realisierter NPV vs Prognose vergleichen, Modell neu lösen.
Alternativen
Manuell + Tabellenkalkulation
KostenlosKeine Lizenzkosten
Für wen geeignet: Kleiner Umfang, 10-30 Kandidaten, ein Budget, einfache Abhängigkeiten
- + Kein Setup
- + Politisch-strategische Komiteeinflussnahme einfach
- + Reicht für eine schnelle Top-N-Diskussion
- − Reihung-mit-Auswahl garantiert nicht die beste Teilmenge — 5-15% Werteverlust typisch
- − Mehrdimensionale Restriktionen lassen sich manuell nicht respektieren
- − Abhängigkeitsstruktur grob (vorrangige Projekte, sich ausschließende Paare)
- − Keine Sensitivitätsanalyse (Budget ±10%)
Open-Source-MIP-Solver + internes Modell
Open SourceLizenzfrei; Eigenentwicklung 4-12 Wochen oder 200K-600K TRY Beratung
Für wen geeignet: Organisation mit OR/Analytics-Team, 50M+ TRY Jahresbudget
- + Keine Lizenzgebühr
- + Projektauswahl-Modelle bilden sich gut auf Open-Source-Solver ab
- + Schnelle Szenarioanalyse (Budget, Arbeitsstunden, Kapazität)
- + Interne Eigentümerschaft — Modell transparent, Annahmen prüfbar
- − Erfordert Optimierungs-Spezialist und Dateningenieur
- − Modellpflege bleibt im Haus
- − Renditeschätz-Rauschen bleibt — Inputqualität entscheidend
Kommerzieller MIP-Solver + internes Modell
EnterpriseJährlich 200K-1.5M TRY Lizenz (TR-Marktbeobachtung); Großkunden 2-5M TRY
Für wen geeignet: Große Holding, 500M+ TRY Jahresbudget, mehrdimensionale Restriktionen
- + Optimum-Lösungsmotor auf Industrie-Niveau
- + Hochleistungs-Parallel-Lösung
- + Reife Modellierschnittstelle (Skripting plus Modellierungssprachen-Unterstützung)
- + Industrieller Support
- − Hohe Lizenzkosten
- − Modellentwicklung intern, Optimierungs-Spezialist nötig
- − Anbieter-Lock-in-Risiko — Solverwechsel kostet 4-12 Wochen
Enterprise-Projektportfolio-Management-Software
EnterpriseJährlich 500K-3M TRY Lizenz (TR-Marktbeobachtung), je Organisation
Für wen geeignet: Multi-Portfolio, Multi-Kategorie, Multi-Geografie-Holding
- + Integrierter Flow vom Vorschlag bis zur Auswahl
- + Abhängigkeitsstruktur (vorrangige Projekte, Ausschlusspaare, Synergierabatt) im UI modellierbar
- + Quartalsweise Neuplanung und realisierter Renditenvergleich eingebaut
- + Komiteeberichte fertig
- − Hohe Lizenz plus 6-12 Monate Roll-out
- − Eingebautes Solvermodul oft begrenzt — bei großen Portfolios unzureichend
- − Anbieter-Lock-in
- − Branchenanpassung verlängert das Projekt
Empfehlung
Im Gespräch fragen
- Welche Varianten unterstützt das Projektauswahl-Modul — 0/1-Auswahl, beschränkte Lot-Anzahl, ein Budget, mehrdimensionale Restriktionen, Gruppen-Auswahl, Set-up-Kosten?
- Welches Verfahren treibt den Solver — Solver mit Optimum-Garantie, dynamisches Programm, Approximation, fortgeschrittene Suche? Typische Lösungszeit für ein 200-1000-Projekte-Portfolio mit mehreren Restriktionen?
- Lässt sich die Abhängigkeitsstruktur (vorrangige Projekte, sich ausschließende Paare, Synergierabatt, Set-up-Kosten) im UI modellieren oder müssen die Regeln von Hand geschrieben werden?
- Sensitivitätsanalyse — bei Budget ±10% oder Arbeitsstunden ±20% Szenarien: welche Projekte ändern sich, ist das Reporting automatisiert?
- Lässt sich die Unsicherheit in Rendite-Inputs modellieren (Auswahl unter Unsicherheit) oder nur Punktschätzungen?
- Wird für mehr-Restriktions-Lösungen der prozentuale Abstand zwischen erreichtem Wert und theoretischer Obergrenze ausgegeben, sodass der Nutzer weiß, ob das Ergebnis optimal oder nahe Optimum ist?
- Erzeugt die Lösung direkt einen Investitionskomitee-Bericht — gewählte Teilmenge, genutzter Budgetanteil, knappe Entscheidungen?
- Bei Vertragsende: in welchem Standardformat können Kandidatendaten, Modellinputs, Lösungs- und Sensitivitätsverlauf exportiert werden?
Technische Details
Anmerkung der Redaktion
Umgangssprachlich heißt das Problem “Projektauswahl”, “Budgetverteilung” oder “Investitionspriorisierung”. Akademisch heißt es Rucksackproblem (Knapsack Problem) — der Name kommt aus der Metapher, einen kapazitätsbeschränkten Rucksack mit der wertvollsten Last zu füllen (Dantzig 1957). Es ist der Urahn diskreter Auswahlprobleme. Es darf nicht mit dem Portfolio-Optimierungsproblem (#018 Markowitz-Mittelwert-Varianz) verwechselt werden: Markowitz liefert kontinuierliche Gewichte (jedem Asset wird ein reellwertiger Anteil zwischen 0% und 100% des Portfolios zugewiesen) und modelliert Risiko über Varianz und Korrelation; der Knapsack ist eine diskrete Wähle-oder-nicht-Entscheidung (xᵢ ∈ {0, 1}) und maximiert Wert unter Budget und NPV. Hinter den meisten klassischen Entscheidungsproblemen liegt ein Knapsack — Investitionsprojektauswahl, Kampagnenauswahl, Cargo-Beladung, Lieferanten-Teilmengenauswahl. Cutting Stock (#005, mehrdimensionales Zuschneiden) und 3D-Bin-Packing (#015) sind enge Verwandte, aber andere Probleme: Knapsack maximiert Wert, Cutting Stock minimiert die Anzahl der Rollen, 3D-Bin-Packing packt Pakete in Behälter. Assortment Planning (#017) ist eine spezialisierte Knapsack-Variante — gekoppelt mit einem Produktnachfragemodell.
Am häufigsten übersehen: der Unterschied zwischen pseudo-polynomiellem DP und dem Komplexitätsklassen-Label. Der Knapsack ist NP-hart — kein in der Bit-Länge der Eingabe polynomieller Algorithmus ist bekannt. Praktiker lesen das als “unlösbar” — falsch. Bellmans DP läuft in O(N×W) — W ist die Kapazität. Beim Kapitalbudget ist W = 50M TRY; man modelliert in Tausend-TRY-Einheiten (W = 50.000), N = 200 Projekte, 10⁷ Operationen — auf moderner Hardware Sekunden. Pseudo-polynomiell: Zeit ist polynomiell im Wert von W (und exponentiell in der Bit-Länge). Konsequenz: bei moderater W (Tausende, Zehntausende) löst DP Millionen-Objekt-Knapsack-Instanzen in Minuten zum Optimum. Im Komitee sollte niemand auf “mathematisches Optimum unerreichbar, also Bauchgefühl” springen — praktische Knapsack-Werkzeuge (MIP, DP) sind für alle verfügbar.
Zweiter übersehener Punkt: Unsicherheit in NPV/Wert-Inputs. Die Knapsack-Mathematik geht von deterministischen Inputs aus. Tatsächlich beruhen NPV-Schätzungen auf 5-Jahres-Projektionen mit ±20-40% Abweichung; bei neuen Technologien und Digitalprojekten noch mehr. Ein klassischer Knapsack-Solver schluckt diese Unsicherheit und gibt eine ‘optimale’ Teilmenge zurück; bei NPV ±20% kann sich die Teilmenge vollständig ändern. Abhilfe: stochastischer Knapsack (Bertsimas und Sim 2003 robuste Optimierung, Worst-Case-Optimum innerhalb einer NPV-Unsicherheitsmenge), chance-constrained Knapsack (Budgetüberschreitungswahrscheinlichkeit höchstens 5%) oder schlicht eine Sensitivitätsanalyse (Projekte, die unter NPV ±20% stabil gewählt bleiben). Dritter übersehener Punkt: Abhängigkeitsstruktur. Der klassische Knapsack nimmt Unabhängigkeit der Objekte an — Werte werden einfach summiert. In der Praxis gibt es Synergien (A + B gemeinsam liefern Extrawert), Ausschluss (A xor B), Vorrang (A → B), Kapazitätsrabatt (A macht B billiger). Diese werden als MIP-Restriktionen modelliert; man muss vom Standard-Knapsack zu einem reicheren MIP wechseln.
Schritt für Schritt — für den Mittelstand
Phase 1 — Erst messen, dann planen. Die letzten 3-5 Jahre Kandidatenprojekte (angenommen plus abgelehnt): vorgeschlagene NPV-Schätzung, realisierter NPV (für die angenommenen), Investitionsbetrag, Arbeitsstunden, Maschinenstunden. NPV-Abweichungsstatistik nach Kategorie (Erweiterung, Modernisierung, Digital, IT) und Größe, Forecast/realisiertes Verhältnis, ±%-Band. Dokumentieren, an welchem Punkt der Jahresplanung Budget und sonstige Restriktionen (Arbeitsstunden, Maschinenstunden, Kategorie-Sub-Budgets) fixiert werden.
Phase 2 — Wissenskapital herausschälen. Typische Abhängigkeiten zwischen Kandidaten (Vorrangketten, sich ausschließende Paare, Kapazitätsrabatt-Synergien). NPV-Zuverlässigkeitsbänder: kleines Standardprojekt ±10%, Digitaltransformation ±30-40%, F&E ±50%. Politische Kategorie-Sub-Budget-Anforderungen (regionale Balance, Sektordiversifikation).
Phase 3 — Pilot. 6-10 Wochen. In einem Jahreszyklus parallel zur bestehenden intuitiven Auswahl Open-Source-MIP laufen lassen. Beide Outputs für dieselbe Kandidatenmenge nebeneinander berichten; Unterschiede erklären (welches Projekt Greedy gewählt hat, welches MIP, warum). Die Entscheidung bleibt beim Komitee; MIP empfiehlt. Erfolgskriterium vorab definieren: MIP-empfohlenes Portfolio mindestens 5% über Greedy-NPV.
Phase 4 — Rollout. 6-12 Monate bis zur vollen Komiteenutzung. Quartalsweise Neuplanung (neue Vorschläge ergänzen, abgesagte Projekte entfernen). Jährliche Sensitivitätsanalyse (Budget ±10%). Stochastischer oder robuster Knapsack erst nach Etablierung der NPV-Unsicherheitsbasis. Quartalsweise Investitionskomitee: MIP-Empfehlung vs genehmigtes Portfolio, knappe Entscheidungen, NPV-Forecast/realisiert-Kalibrierung.
Risiken — was schiefgehen kann
- NPV-/Renditeschätzfehler. Die Knapsack-Lösung ist mathematisch optimal zu den gegebenen NPVs; ändert sich NPV ±20-40%, kann sich die optimale Teilmenge ändern. Robuste oder stochastische Knapsack-Erweiterung oder mindestens Sensitivitätsanalyse (Projekte, die unter NPV ±20% stabil sind) sind Pflicht. Zur Forecast-Kalibrierung über Zeit realisierter NPV / Forecast-NPV nach Kategorie verfolgen.
- Projektunabhängigkeitsannahme. Der klassische Knapsack summiert Objektwerte; in der Praxis gibt es Synergien (A + B gemeinsam zusätzlicher Wert), Ausschluss (A xor B), Vorrang (A → B), Kapazitätsrabatt (A macht B billiger). Diese erfordern MIP-Restriktionen; man muss die Standard-Knapsack-Oberfläche verlassen.
- Risikoverteilung wird ignoriert. Reiner Knapsack maximiert den Gesamtwert; er modelliert Portfoliorisiko (Varianz, Kovarianz, Tail-Risiko) nicht. Fünf Projekte im selben Sektor können hohen NPV liefern, aber das Portfolio bei einem Sektor-Schock fragil machen. Sektor- / Geografie- / Kategorie-Sub-Budget-Restriktionen ergänzen, oder Knapsack-Auswahl mit CVaR-artigem Risikomaß (#063) koppeln.
- Anbieter-Lock-in bei Investitionsplanungssoftware. Ohne Vertragsklausel zum jährlichen Export von Kandidatendaten, Modellinputs, Lösungs- und Sensitivitätsverlauf in einem Standardformat bedeutet ein Anbieterwechsel den Verlust des Investitionsgedächtnisses. Open-Source-MIP + internes Modell liefert in mittlerer Größenordnung Anbieterunabhängigkeit.
Technischer Blick auf die Lösung
| Ansatz | Typische Größe | Lösungszeit | Optimalitätsgarantie? |
|---|---|---|---|
| Greedy (nach NPV/Investition sortieren) | Beliebig | sofort | Nein (85-95% Optimum typisch) |
| LP-Relaxierungs-Obergrenze | Beliebig | sofort | Nein (Obergrenze) |
| Dynamic Programming (Bellman 1957) | Moderat (N≤1000, W≤10⁶) | Sekunden-Minuten | Ja |
| Branch-and-Bound (Martello-Toth 1990) | Mittel-groß 0/1-KP | Minuten-Stunden | Ja |
| Pisinger Expanding Core (1997) | Sehr groß 0/1-KP | Minuten | Ja |
| MIP (allgemein) | Allgemein (MKP, QKP, Set-up) | Sekunden-Stunden | Ja (innerhalb Gap) |
| FPTAS (Ibarra-Kim 1975) | Sehr groß, ε-Approx OK | Minuten | (1-ε)-Optimum |
| Metaheuristik (genetisch, Tabu, SA) | Sehr großes MKP, abhängigkeitsreich | Minuten-Stunden | Nein, gute praktische Qualität |
Knapsack-Varianten im Vergleich:
- 0/1-Knapsack: jedes Objekt einmal oder gar nicht. Klassische Kapitalbudgetierung.
- Bounded Knapsack: beschränkte Kopienzahl. Lieferantenlots.
- Unbounded Knapsack: unbegrenzte Kopienzahl. Kapazitätsbeschränkte Produktion, ganzzahlige Aktienlots.
- Multi-Dimensional Knapsack (MKP): m Restriktionen — Budget + Arbeit + Maschine + Kategorie.
- Quadratic Knapsack (QKP): paarweise Synergie- oder Wechselwirkungsterme.
- Multiple-Choice MKP: Objekte gruppiert, je Gruppe genau eines (Modul-Bundles).
- Subset-Sum: Zielwert = Gewicht; Gesamt möglichst nah an Kapazität.
- Knapsack mit Set-Up: fixe Set-up-Kosten je Gruppe.
Zielfunktions-Wahl:
- Ziel 1 — Maximum Gesamtwert (NPV, Conversion-Wert): klassisch.
- Ziel 2 — Maximum Budgetauslastung (Subset-Sum-nah): Disziplin der Vollauslastung.
- Ziel 3 — Robust / Worst Case (über NPV-Unsicherheitsmenge): Bertsimas-Sim robuste Optimierung.
- Ziel 4 — Erwartungswert minus Varianzstrafe (stochastisch): Mittelwert-Varianz-Knapsack.
Abhängigkeitsmodellierung (im MIP):
- Vorrang (A → B): xB ≤ xA.
- Ausschluss (A xor B): xA + xB ≤ 1.
- Synergierabatt: Zusatzvariable yA·B.
- Set-up: Zusatzvariable yk pro Gruppe.
- Kategorie-Sub-Budget: Σᵢ∈Cwᵢxᵢ ≤ Wc je Kategorie C.
Akademische Quellen
Im Frontmatter unter sources aufgeführt.
Quellen
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. Grundlegende Quelle der LP/IP-Formulierung des Knapsack-Problems.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. Grundbuch der dynamischen Programmierung; Knapsack ist das kanonische Beispiel.
- Martello, S. und Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. Klassisches Lehrbuch; Branch-and-Bound, experimentelle Vergleiche.
- Kellerer, H., Pferschy, U. und Pisinger, D. (2004). Knapsack Problems. Springer. Moderne umfassende Referenz; alle Varianten, FPTAS, MKP, QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. Praktischer State of the Art mit Expanding-Core für 0/1-Knapsack.
- Ibarra, O. H. und Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. Grundlegende Quelle des Knapsack-FPTAS.
- YÖK Tez Merkezi — Stichworte: ‘sırt çantası’, ‘knapsack’ oder ‘proje seçimi’ — 25+ Arbeiten aus der TR-Akademie. tez.yok.gov.tr
Glossar
- Knapsack Problem
- Das grundlegende diskrete Optimierungsproblem, aus N Objekten mit je einem Wert und einem Gewicht eine Teilmenge auszuwählen, die den Gesamtwert unter einer Kapazitätsschranke maximiert.
- Dynamic Programming
- Die OR / Informatik-Technik zur Lösung mehrstufiger Entscheidungsprobleme durch rekursive Zerlegung in überlappende Teilprobleme mit gespeicherten Zwischenresultaten; eingeführt von Bellman (1957).
- MIP
- Optimierungsmodell, bei dem ein Teil der Entscheidungsvariablen ganzzahlig sein muss (z. B. Anzahl LKW, Anzahl Schichten).
Ähnliche Probleme
Mehrere Inputs + mehrere Outputs — Wie messe ich die relative Effizienz meiner Filialen oder Einheiten?
Diese Seite richtet sich an Sie, wenn Sie eine Bank mit 100-500 Filialen, eine Krankenhauskette mit 200-1.500 Betten an mehreren Standorten, eine Bildungsdirektion mit Hunderten von Schulen oder eine öffentliche Stelle führen, die Provinz für Provinz vergleicht. Die Kernfrage: welche Ihrer Filialen/Kliniken/Schulen sind effizient und welche nicht — und an welchem 'Peer' sollen sich die schwachen orientieren, um wie viel zu schließen? Jede Einheit verbraucht gleichzeitig mehrere Inputs (Personal, Fläche, Budget) und produziert mehrere Outputs (Erträge, Kunden/Patienten/Schüler, Qualität); eine Einzelkennzahl wie 'Ertrag pro Mitarbeiter' bildet das nicht ab und kann eine effiziente Einheit als schwach ausweisen oder umgekehrt. Richtig aufgesetzt — weil der Peer-Benchmark einen konkreten Verbesserungsbezug liefert — steigt die Akzeptanz von Verbesserungsplänen für schwache Einheiten um 40-70%, was bei einem mittelgroßen Filialnetz grob 10-50 Millionen TRY operativer Marge pro Jahr entspricht.
Welcher Anteil meines Geldes geht in welche Anlage?
Eine Grundfrage für KMU oder Privatanleger: Es gibt Kapital und mehrere Anlageoptionen (Aktien, Anleihen, FX, Rohstoffe, Termingeld, Immobilien, Reinvestition im Unternehmen), jede mit eigener erwarteter Rendite und Risiko und mit Korrelationen untereinander. Wie viel Prozent geht wohin? Der mathematische Name ist Portfolio Optimization Problem. 1952 stellte Harry Markowitz den Mean-Variance-Rahmen vor — das Nobelpreis-gekrönte Fundament der modernen Portfoliotheorie. Erwartete Rendite maximieren bei minimaler Varianz (Risiko) ist ein quadratisches Optimierungsproblem.