Zum Inhalt springen
Zurück zu den Suchergebnissen

Mixed-Integer Programming — Exakte Optimierung über kontinuierliche und ganzzahlige Entscheidungen

Eingeführt von
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
Jahr
1958–1960
Typ
Mathematical 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?

Mixed-Integer Programming (MIP) ist ein mathematischer Optimierungsrahmen, in dem einige Entscheidungsvariablen ganzzahlige Werte annehmen müssen, während andere kontinuierlich sein dürfen.

Es verallgemeinert die lineare Programmierung und wird häufig in der betrieblichen Forschung, Logistik, Zeitplanung, Ressourcenallokation und im Ingenieurwesen eingesetzt, wo natürliche Unteilbarkeitsbeschränkungen – wie Ja/Nein-Entscheidungen oder ganze Einheitenmengen – auftreten.

Die Intuition hinter der Methode

Viele reale Optimierungsprobleme beinhalten Entscheidungen, die nicht geteilt werden können – man eröffnet eine Anlage oder nicht, man weist genau einen Mitarbeiter einer Schicht zu, man bestellt ganze Einheiten. Kontinuierliche lineare Programmierung ignoriert diese Realitäten und kann nicht implementierbare gebrochene Antworten liefern. MIP erzwingt die Ganzzahligkeit direkt im Modell. Der Solver durchsucht den Raum zulässiger ganzzahliger Lösungen systematisch mittels Branch-and-Bound: Er löst relaxierte kontinuierliche Teilprobleme, um die bestmögliche Lösung in jeder Region zu begrenzen, verwirft Regionen, die die bisher beste gefundene ganzzahlige Lösung nicht verbessern können, und fügt Schnittebenen hinzu, um die Suche zu verfeinern. Das Ergebnis ist ein nachweislich optimaler oder nahezu optimaler Plan.

Geschichte

Die Grundlagen der ganzzahligen Programmierung wurden von Ralph Gomory gelegt, der 1958 die Schnittebenenmethode einführte, und von Land und Doig, die 1960 Branch-and-Bound formalisierten. In den folgenden Jahrzehnten wurden die LP-Relaxierungstheorie, die polyedrische Kombinatorik (Edmonds, Padberg, Grötschel) entwickelt, und in den 1990er Jahren machten kommerzielle Lösungsalgorithmen MIP im großen Maßstab praktikabel. Das Feld wird umfassend in Nemhauser und Wolsey (1988) und Wolsey (1998) behandelt.

Wann wird sie eingesetzt?

Verwenden Sie MIP, wenn Ihr Problem eine lineare oder linearisierbare Zielfunktion und Beschränkungen hat und Entscheidungen beinhaltet, die ganzzahlig sein müssen (Standortwahl von Anlagen, Besatzplanung, Kapitalbudgetierung, Netzwerkauslegung, Zuschnittprobleme). Es ist die Methode der Wahl, wenn Sie eine nachweislich optimale oder eine Lösung mit begrenzter Lücke benötigen und die Problemgröße handhabbar ist (Tausende von Variablen mit modernen Lösungsalgorithmen). Verwenden Sie MIP NICHT, wenn die Zielfunktion oder die Beschränkungen stark nichtlinear sind (verwenden Sie stattdessen nichtlineare oder gemischt-ganzzahlige nichtlineare Programmierung), wenn das Problem so groß ist, dass exakte Methoden unerschwinglich sind (erwägen Sie Heuristiken oder Metaheuristiken) oder wenn kontinuierliche Näherungen genau genug sind (verwenden Sie LP für Geschwindigkeit).

Grenzen und Hinweise

  • Die Worst-Case-Komplexität ist NP-schwer; die Lösungszeit kann exponentiell mit der Anzahl der ganzzahligen Variablen ansteigen.
  • Erfordert eine präzise mathematische Formulierung; schlecht formulierte Modelle können selbst bei überschaubarem zugrundeliegendem Problem unlösbar sein.
  • Nicht-konvexe oder nichtlineare Elemente erfordern zusätzliche Linearisierung oder spezialisierte Lösungsalgorithmen, was die Modellkomplexität erhöht.
  • Lizenzkosten für Lösungsalgorithmen können für kommerzielle Werkzeuge erheblich sein, obwohl qualitativ hochwertige Open-Source-Alternativen existieren.
  • Die Ergebnisse sind nur so gut wie das Modell: Falsche Spezifikation von Beschränkungen führt zu bedeutungslosen Optima.

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

Stärken

  • Liefert nachweislich optimale Lösungen mit einer quantifizierbaren Optimalitätslücke, was eine rigorose Entscheidungsbegründung ermöglicht.
  • Behandelt binäre und allgemeine ganzzahlige Variablen nativ und erfasst reale Unteilbarkeits- und logische Beschränkungen.
  • Moderne Lösungsalgorithmen (Gurobi, CPLEX, SCIP) nutzen fortschrittliche Branch-and-Bound-, Schnittebenen- und Vorverarbeitungstechniken, um große Instanzen effizient zu bearbeiten.
  • Die transparente Modellformulierung macht Annahmen explizit und überprüfbar durch Fachexperten.
  • Unterstützt Sensitivitätsanalysen und parametrische Studien, um zu verstehen, wie sich Lösungen mit Eingabedaten ändern.
  • Weit verbreitet von Modellierungssprachen (AMPL, GAMS, Pyomo, JuMP) unterstützt, was schnelles Prototyping ermöglicht.

Anwendungen

  • Lieferketten und Logistik: Fahrzeugroutenplanung, Standortwahl von Anlagen und Lageroptimierung mit ganzzahligen Versandmengen.
  • Personalplanung: Dienstplanerstellung für Pflegekräfte, Besatzplanung und Schichtplanung mit binären Zuordnungsvariablen.
  • Kapitalbudgetierung: Auswahl eines Portfolios von unteilbaren Investitionsprojekten unter Budgetbeschränkungen.
  • Telekommunikation und Netzwerkauslegung: Kapazitätserweiterung und Routenplanung mit binären Entscheidungen zur Aktivierung von Verbindungen.
  • Energiesysteme: Unit Commitment in Stromnetzen, bei dem entschieden wird, welche Generatoren jede Stunde ein- oder ausgeschaltet werden.
  • Fertigung: Produktionslosgrößenermittlung, Maschinenplanung und Zuschnittprobleme mit ganzzahligen Chargengrößen.

So funktioniert es

So funktioniert es

1

Definieren Sie das Optimierungsmodell: eine Zielfunktion (lineare Kombination von Entscheidungsvariablen zur Minimierung oder Maximierung), lineare Ungleichungs- und Gleichheitsbeschränkungen sowie Ganzzahligkeitsanforderungen. Kontinuierliche Variablen behandeln Mengen, die gebrochen sein können; binäre (0/1) oder allgemeine ganzzahlige Variablen behandeln diskrete Entscheidungen.

Formel
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

Lösen Sie die LP-Relaxierung, indem Sie vorübergehend die Ganzzahligkeitsbeschränkungen fallen lassen. Dies ergibt eine untere Schranke (bei Minimierung) für die optimale MIP-Zielfunktion und eine Kandidatenlösung, die gebrochen sein kann.

Formel
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

Wählen Sie eine gebrochene ganzzahlige Variable aus der LP-Relaxierungslösung. Erstellen Sie zwei Kind-Teilprobleme, indem Sie in einem eine Bodenbeschränkung und in der anderen eine Deckenbeschränkung hinzufügen, wodurch der zulässige Raum aufgeteilt wird, ohne einen ganzzahligen zulässigen Punkt zu verlieren.

Formel
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

Lösen Sie die LP-Relaxierung jedes Teilproblems. Wenn die Schranke schlechter ist als die bisher beste gefundene ganzzahlige Lösung (der Inkumbent), verwerfen Sie diesen Zweig. Wenn die LP-Lösung zufällig ganzzahlig zulässig ist, aktualisieren Sie den Inkumbenten, falls er die Zielfunktion verbessert.

Formel
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

Fügen Sie optional Schnittebenen hinzu – gültige Ungleichungen, die die gebrochene LP-Lösung abschneiden, ohne einen ganzzahligen zulässigen Punkt zu entfernen. Gomory-Schnitte sind der klassische Ansatz; problemspezifische Schnitte (z. B. Clique-Schnitte, Flow-Schnitte) können die Baumgröße dramatisch reduzieren.

Formel
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

Stoppen Sie, wenn der Branch-and-Bound-Baum vollständig durchsucht ist oder wenn die Lücke zwischen der besten ganzzahligen Lösung und der globalen unteren Schranke innerhalb einer vom Benutzer angegebenen Toleranz (z. B. 0,01 %) liegt. Geben Sie die Inkumbenten-Lösung mit ihrem Optimalitätszertifikat zurück.

Formel
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

Häufige Fallstricke

  • Die Wahl einer zu engen Optimalitätslückentoleranz kann dazu führen, dass der Lösungsalgorithmus unendlich lange läuft; setzen Sie immer eine praktische Lücke (z. B. 1 %) für große Instanzen.
  • Symmetrie im Modell (z. B. austauschbare Anlagen) erzeugt redundante Zweige und bläht den Suchbaum auf – verwenden Sie Symmetrie-brechende Beschränkungen.
  • Schwache LP-Relaxierungen (große Ganzzahligkeitslücke) führen zu sehr großen Branch-and-Bound-Bäumen; investieren Sie Zeit in das Hinzufügen gültiger Ungleichungen oder die Verfeinerung der Formulierung.
  • Alle Variablen als ganzzahlig zu behandeln, wenn nur einige es sein müssen, ist unnötig kostspielig; verwenden Sie binäre Variablen nur dort, wo logische Beschränkungen dies erfordern.
  • Das Ignorieren des Warmstarts mit einer guten anfänglichen zulässigen Lösung verschwendet Zeit des Lösungsalgorithmus bei der Suche nach dem ersten Inkumbenten.

Häufig gestellte Fragen

Wie unterscheidet sich MIP von der linearen Programmierung (LP)?

LP erfordert, dass alle Entscheidungsvariablen kontinuierlich (reellwertig) sind, was zu gebrochenen Lösungen führen kann, die physikalisch nicht zulässig sind (z. B. 2,7 Lkw). MIP fügt Ganzzahligkeitsbeschränkungen für einige oder alle Variablen hinzu und erzwingt ganzzahlige oder binäre Lösungen auf Kosten einer größeren rechnerischen Komplexität.

Wann sollte ich eine Heuristik anstelle von MIP verwenden?

Wenn das Problem Millionen von Variablen, eine stark nichtlineare Struktur hat oder eine nahezu Echtzeitlösung erfordert, kann exaktes MIP zu langsam sein. Metaheuristiken (genetische Algorithmen, Simulated Annealing) können schnell gute Lösungen liefern, jedoch ohne Optimalitätsgarantien. MIP wird bevorzugt, wenn die Zertifizierung der Lösungsqualität wichtig ist.

Was ist die Optimalitätslücke und wie klein sollte sie sein?

Die Lücke ist (Inkumbenten-Zielfunktion - LP-Schranke) / LP-Schranke, ausgedrückt als Prozentsatz. Sie bescheinigt, wie weit die beste bekannte ganzzahlige Lösung vom wahren Optimum entfernt sein kann. Für die meisten praktischen Anwendungen ist eine Lücke von 0,1–1 % ausreichend; engere Lücken erfordern exponentiell mehr Lösungszeit.

Kann MIP nichtlineare Zielfunktionen oder Beschränkungen behandeln?

Standard-MIP geht von Linearität aus. Nichtlineare Beziehungen müssen linearisiert werden (z. B. stückweise lineare Approximation, binäre Erweiterung von Produkten) oder von MINLP-Lösungsalgorithmen (Mixed-Integer Nonlinear Programming) behandelt werden, die deutlich schwieriger zu lösen sind.

Welche Lösungsalgorithmen werden für MIP empfohlen?

Kommerziell: Gurobi und CPLEX sind die Branchenmaßstäbe. Open Source: SCIP, CBC (über COIN-OR) und HiGHS sind für mittelgroße Probleme wettbewerbsfähig. Alle unterstützen Standard-Modellierungsschnittstellen wie AMPL, Pyomo und JuMP.

Verwandte Methoden

Quellen

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    ISBN: 9780471359432
    Kopiert.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Kopiert.