Zum Inhalt springen
Zurück zu den Suchergebnissen

Deterministisches Ganzzahlige Programmierung — Exakte Optimierung mit ganzzahligen Entscheidungsvariablen

Eingeführt von
Ralph E. Gomory
Jahr
1958
Typ
Exact combinatorial optimization
Familie
Simulation / optimization

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Die deterministische ganzzahlige Programmierung (DIP) ist ein mathematischer Optimierungsansatz, der die beste Lösung für Probleme findet, bei denen einige oder alle Entscheidungsvariablen ganzzahlige Werte annehmen müssen, unter der Annahme vollständig bekannter (deterministischer) Zielfunktions- und Nebenbedingungsdaten.

Sie ist die klassische, nicht-stochastische Form der ganzzahligen Programmierung und seit den späten 1950er Jahren ein Grundpfeiler der Operations Research und der kombinatorischen Optimierung.

Die Intuition hinter der Methode

Viele reale Entscheidungen sind inhärent diskret: Man eröffnet eine Anlage oder nicht; man teilt einen Arbeiter einer Schicht zu oder nicht. Kontinuierliche Optimierungsmethoden können diese Ganzzahlanforderungen nicht erzwingen. Die deterministische ganzzahlige Programmierung handhabt dies, indem sie Variablen auf ganze Zahlen beschränkt, während alle Problemparameter – Kosten, Kapazitäten, Bedarfe – mit Sicherheit bekannt sind. Das Ergebnis ist eine exakte, nachweislich optimale Lösung unter dieser Annahme der Sicherheit, was sie zur Referenzformulierung macht, mit der stochastische und robuste Varianten verglichen werden.

Geschichte

Die ganzzahlige Programmierung entstand Ende der 1950er Jahre aus der linearen Programmierung. Ralph Gomorys Algorithmus für schneidende Ebenen von 1958 war die erste systematische exakte Methode. Parallel zum Branch-and-Bound (Land und Doig, 1960) definierten diese Ansätze das Feld. Das Adjektiv 'deterministisch' unterscheidet die klassische Formulierung von der stochastischen ganzzahligen Programmierung (Birge und Louveaux, 1997) und wurde zur Standardterminologie, als unsicherheitsbewusste Varianten aufkamen.

Wann wird sie eingesetzt?

Verwenden Sie deterministische ganzzahlige Programmierung, wenn: (1) Entscheidungsvariablen inhärent diskret sind (Zuordnung, Zeitplanung, Standortwahl, Behälterpacken, Netzdesign); (2) alle Problemparameter mit Sicherheit bekannt sind oder zuverlässig als Punktwerte geschätzt werden können; (3) eine exakte optimale Lösung erforderlich ist und keine heuristische Annäherung. NICHT verwenden, wenn: Parameter unsicher oder szenarioabhängig sind (verwenden Sie stattdessen stochastische oder robuste ganzzahlige Programmierung); die Problemgröße so groß ist, dass Branch-and-Bound rechnerisch nicht handhabbar ist und Heuristiken akzeptabel sind; Variablen wirklich kontinuierlich sind (verwenden Sie LP); oder mehrere widersprüchliche Ziele gleichzeitig ausgeglichen werden müssen (verwenden Sie mehrzielige ganzzahlige Programmierung).

Grenzen und Hinweise

  • Geht davon aus, dass alle Problemparameter exakt bekannt sind – reale Unsicherheiten werden per Design ignoriert.
  • Im Allgemeinen NP-schwer; die Lösungszeit im Worst-Case wächst exponentiell mit der Problemgröße.
  • Große kombinatorische Probleme können selbst mit modernen Solvern Stunden oder Tage Rechenzeit erfordern.
  • Die Qualität der Modellformulierung (Engheit der Nebenbedingungen, Symmetriebrechung) beeinflusst die Lösungszeit erheblich.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Garantiert eine nachweislich optimale Lösung unter den Annahmen des deterministischen Modells.
  • Behandelt natürlich diskrete, kombinatorische Entscheidungsstrukturen, die kontinuierliche Methoden nicht bewältigen können.
  • Unterstützt durch ausgereifte, hocheffiziente kommerzielle und Open-Source-Solver (CPLEX, Gurobi, SCIP).
  • Bietet ein Optimalitätslückenzertifikat, das eine prinzipienfeste frühe Beendigung für große Instanzen ermöglicht.
  • Dient als Goldstandard-Benchmark-Formulierung für den Vergleich von heuristischen und stochastischen Varianten.

Anwendungen

  • Produktionsplanung und -terminierung mit diskreten Maschinen- oder Arbeitsressourcen
  • Standortwahl: Entscheidung, welche Lager oder Werke eröffnet werden sollen
  • Fahrzeugroutenplanung und Besatzplanung im Transportwesen und in der Logistik
  • Kapitalbudgetierung: Auswahl eines Portfolios von unteilbaren Investitionsprojekten
  • Design von Telekommunikationsnetzen mit festen Kosten für den Leitungsaufbau
  • Dienstplangestaltung für Gesundheitspersonal und Terminplanung von Operationssälen

So funktioniert es

So funktioniert es

1

Definieren Sie das Optimierungsmodell: eine Zielfunktion, die als lineare Kombination von ganzzahligen Entscheidungsvariablen minimiert (oder maximiert) werden soll, unter Berücksichtigung einer Reihe von linearen Ungleichungs- oder Gleichungsnebenbedingungen. Alle Koeffizienten (c, A, b) sind fest und bekannt – das macht die Formulierung deterministisch. Binäre Variablen (0/1) sind ein Sonderfall für Ja/Nein-Entscheidungen.

Formel
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

Lösen Sie die LP-Relaxierung, die Variablen vorübergehend kontinuierliche Werte annehmen lässt. Dies liefert eine untere Schranke für das optimale ganzzahlige Ziel. Wenn die Lösung der LP-Relaxierung bereits ganzzahlig ist, ist sie optimal für die IP; andernfalls beginnt das Branching.

Formel
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

Wählen Sie eine variable mit gebrochenem Wert aus der Lösung der LP-Relaxierung und teilen Sie den zulässigen Bereich auf, indem Sie auf einem Zweig eine Bodenbedingung (x_j <= floor value) und auf dem anderen eine Deckenbedingung (x_j >= ceil value) hinzufügen, wodurch zwei Teilprobleme erzeugt werden, die rekursiv gelöst werden müssen.

Formel
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

Lösen Sie die LP-Relaxierung jedes Teilproblems, um eine Schranke zu erhalten. Wenn die Schranke eines Knotens schlechter ist als die beste bekannte ganzzahlige Lösung (Inkumbent), verwerfen Sie ihn. Wenn das Teilproblem eine ganzzahlig zulässige Lösung liefert, die besser ist als der Inkumbent, aktualisieren Sie den Inkumbenten. Der Prozess bildet einen Branch-and-Bound-Suchbaum.

Formel
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

Schneidende-Ebenen-Methoden – insbesondere Gomory-Schnitte – leiten zusätzliche lineare Ungleichungen aus dem LP-Tableau ab, die von allen ganzzahligen Lösungen erfüllt, aber von der aktuellen gebrochenen LP-Lösung verletzt werden. Das Hinzufügen dieser Schnitte verschärft die LP-Relaxierung und reduziert das Branching. Moderne Solver kombinieren Branch-and-Bound mit Schnitten in einem Branch-and-Cut-Framework.

Formel
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

Der Algorithmus endet, wenn alle offenen Knoten verworfen werden oder ganzzahlige Lösungen liefern. Der Inkumbent zum Zeitpunkt der Beendigung ist die nachweislich optimale ganzzahlige Lösung. Solver berichten auch über eine Lücke zwischen der besten Schranke und dem Inkumbenten, die als Abbruchkriterium für große Probleme verwendet werden kann.

Formel
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

Häufige Fallstricke

  • Die Behandlung unsicherer Parameter als deterministische Punktwerte kann zu Lösungen führen, die sich in der Praxis schlecht bewähren – validieren Sie diese Annahme, bevor Sie DIP anwenden.
  • Schwache LP-Relaxierungen (große Integritätslücken) führen zu enormen Branch-and-Bound-Bäumen; investieren Sie in gültige Ungleichungen und Umformulierung, bevor Sie die Skalierung erhöhen.
  • Die Explosion binärer Variablen durch Big-M-Formulierungen kann die LP-Relaxierung numerisch destabilisieren; bevorzugen Sie engere Nebenbedingungs-Umformulierungen.
  • Fehlinterpretation von Zulässigkeit als Optimalität bei Verwendung einer Toleranz für eine Nicht-Null-Lücke – berichten Sie immer die Lücke zusammen mit dem Zielwert.
  • Das Ignorieren von Symmetrien in Modellen (z. B. identische Maschinen oder Arbeiter) verursacht redundantes Branching; fügen Sie Symmetrie-brechende Nebenbedingungen hinzu.

Häufig gestellte Fragen

Was unterscheidet die deterministische von der stochastischen ganzzahligen Programmierung?

Bei der deterministischen IP sind alle Ziel- und Nebenbedingungsparameter fest und bekannt. Die stochastische IP modelliert unsichere Parameter explizit über Wahrscheinlichkeitsverteilungen oder Szenarien und liefert Lösungen, die über diese Szenarien hinweg robust oder im Erwartungswert optimal sind. Die deterministische IP ist einfacher und schneller zu lösen, ignoriert aber Unsicherheiten.

Ist binäre Programmierung ein Sonderfall der ganzzahligen Programmierung?

Ja. Die binäre (0-1) Programmierung beschränkt jede Entscheidungsvariable auf {0, 1}. Sie ist der häufigste Sonderfall und wird für Ja/Nein-Entscheidungen verwendet, wie z. B. ob eine Anlage eröffnet, ein Projekt ausgewählt oder ein Arbeiter zugewiesen werden soll. Die allgemeine ganzzahlige Programmierung erlaubt jeden nicht-negativen ganzzahligen Wert.

Wann sollte ich von deterministischer IP zu einer heuristischen Methode wechseln?

Wenn der Branch-and-Bound-Baum zu groß ist, um ihn innerhalb eines akzeptablen Zeitlimits zu durchsuchen, und die Optimalitätslücke einer guten Heuristik (genetischer Algorithmus, simulierte Abkühlung, Large Neighborhood Search) für die Anwendung tolerierbar ist. Berichten und rechtfertigen Sie die Lücke, wenn Sie von exakter Optimierung abweichen.

Kann deterministische IP nichtlineare Ziele oder Nebenbedingungen behandeln?

Die klassische deterministische IP nimmt Linearität an (ganzzahlige lineare Programmierung). Nichtlineare ganzzahlige Programmierung existiert, ist aber wesentlich schwieriger; viele nichtlineare Formen können durch Hilfsbinärvariablen und Big-M-Umformulierungen linearisiert werden. Quadratische ganzzahlige Programmierung (QIP) wird von einigen modernen Solvern direkt unterstützt.

Welchen Solver sollte ich in der Praxis für deterministische IP verwenden?

Kommerziell: Gurobi oder IBM CPLEX für beste Leistung. Akademisch/Open-Source: SCIP, CBC (über COIN-OR) oder HiGHS. Alle implementieren Branch-and-Cut mit automatischer Vorverarbeitung. Für Python-Benutzer bieten PuLP, Pyomo oder scipy.optimize.milp bequeme Modellierungsschnittstellen.

Verwandte Methoden

Quellen

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    DOI-Referenz öffnen
    Kopiert.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Kopiert.