Ganzzahlige Programmierung — IP und gemischt-ganzzahlige Programmierung (MIP)
- Eingeführt von
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Jahr
- 1958
- Typ
- Mathematical optimisation — exact combinatorial method
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Ganzzahlige Programmierung (IP), auch gemischt-ganzzahlige Programmierung (MIP) genannt, wenn nur einige Variablen auf ganze Zahlen beschränkt sind, ist ein Zweig der mathematischen Optimierung, bei dem einige oder alle Entscheidungsvariablen ganzzahlige oder binäre Werte annehmen müssen.
Aufbauend auf der linearen Programmierung wurde sie durch Ralph Gomorys Schnittebenenmethode (1958) und den Land-und-Doig-Branch-and-Bound-Algorithmus (1960) formalisiert und ist seitdem der Standard-Exakt-Rahmen für Planungs-, Zuordnungs-, Routen- und Ressourcenzuweisungsprobleme geworden.
Die Intuition hinter der Methode
Die gewöhnliche lineare Programmierung findet den besten Punkt in einem kontinuierlichen zulässigen Bereich. Aber viele reale Entscheidungen sind diskret – man kann keine 2,7 Krankenschwestern einstellen oder ein halbes Lager eröffnen. Die ganzzahlige Programmierung fügt die Beschränkung hinzu, dass einige oder alle Variablen ganze Zahlen (oder binäre 0/1-Entscheidungen) sein müssen. Der Preis dieser Beschränkung ist rechnerisch: Die zulässige Menge ist keine glatte Oberfläche mehr, sondern eine verstreute Menge von Punkten, und die Suche nach dem besten kann die Untersuchung einer enormen Anzahl von Kandidatenlösungen erfordern. Solver verwalten dies, indem sie das Problem intelligent in kleinere Teilprobleme aufteilen (Branching) und Zweige abschneiden, die die bisher beste gefundene Lösung nicht übertreffen können (Bounding), während sie gleichzeitig die kontinuierliche Annäherung durch zusätzliche Ungleichungen (Schnittebenen) verschärfen.
Geschichte
Die ganzzahlige Programmierung entstand Ende der 1950er Jahre, als Forscher versuchten, die lineare Programmierung auf diskrete Entscheidungen auszuweiten. Ralph Gomory führte 1958 die systematische Schnittebenenmethode ein und bewies, dass jedes ganzzahlige Programm prinzipiell durch Hinzufügen endlich vieler Schnitte gelöst werden kann. Land und Doig (1960) formalisierten Branch-and-Bound, das zum dominierenden exakten Algorithmus wurde. Wolsey (1998) und Nemhauser und Wolsey (1988) lieferten die kanonischen Lehrbuchdarstellungen, auf denen das Feld noch heute beruht. Die praktische Revolution kam mit der Entwicklung von Branch-and-Cut-Solvern in den 1990er Jahren, die beide Techniken mit fortschrittlichen Heuristiken kombinierten, und später mit der Explosion der Leistung kommerzieller und Open-Source-Solver, die heute groß angelegte reale Anwendungen ermöglichen.
Wann wird sie eingesetzt?
Verwenden Sie ganzzahlige Programmierung, wenn Entscheidungen inhärent diskret sind – binäre Ja/Nein-Entscheidungen, ganzzahlige Mengen oder logische Ein/Aus-Beschränkungen – und wenn Sie eine exakte oder nahezu exakte optimale Lösung mit einer nachweisbaren Qualitätsgrenze benötigen. Sie eignet sich für Planungs-, Besatz- und Ressourcenzuweisung, Fahrzeugroutenplanung, Standortplanung, Kapitalbudgetierung und Portfolioselektion. Es gibt keine Mindeststichprobengröße, da IP ein deterministisches Optimierungsframework und keine statistische Inferenzprozedur ist. Variablentypen können binär, kategorial (als binär kodiert) oder kontinuierlich (im gemischt-ganzzahligen Fall) sein. Die wichtigste praktische Anforderung ist, dass das Problem mit einer linearen Zielfunktion und linearen Beschränkungen modelliert werden kann; wenn die Zielfunktion oder die Beschränkungen nichtlinear sind, sind Erweiterungen der gemischt-ganzzahligen nichtlinearen Programmierung (MINLP) erforderlich.
Grenzen und Hinweise
- Die ganzzahlige Programmierung ist im Allgemeinen NP-schwer; die Lösungszeit kann exponentiell mit der Problemgröße und schlechter Formulierung wachsen.
- Eine schwache LP-Relaxation (große Ganzzahligkeitslücke) führt zu tiefen, teuren Suchbäumen und langen Laufzeiten.
- Die binäre Erweiterung von kategorialen Variablen mit hoher Kardinalität kann die Modellgröße aufblähen.
- Für sehr große Instanzen müssen Solver möglicherweise frühzeitig mit einer Lückentoleranz beendet werden, anstatt eine Null-Lücke zu erreichen.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Liefert exakte optimale Lösungen mit einer zertifizierten Optimalitätslücke, im Gegensatz zu Heuristiken, die keine Qualitätsgarantie bieten.
- Verarbeitet binäre und allgemeine ganzzahlige Variablen nativ und ist somit der natürliche Rahmen für kombinatorische Entscheidungen.
- Anwendbar auf eine breite Palette von Domänenproblemen – Planung, Routenplanung, Zuweisung, Rucksackproblem – mit derselben mathematischen Maschinerie.
- Moderne Branch-and-Cut-Solver können Probleme mit Millionen von Variablen und Beschränkungen lösen, die vor Jahrzehnten unlösbar gewesen wären.
Anwendungen
- Personal- und Krankenschwesternplanung – Zuweisung von Schichten zur Erfüllung von Abdeckungsvorgaben unter Einhaltung von Arbeitszeitvorschriften.
- Fahrzeugroutenplanung und Logistik – Ermittlung von Routen mit minimalen Kosten für die Lieferung unter Berücksichtigung von Kapazitäts- und Zeitfensterbeschränkungen.
- Standortplanung – Entscheidung, welche Lager oder Werke eröffnet werden sollen, um die gesamten Vertriebskosten zu minimieren.
- Kapitalbudgetierung – Auswahl eines Portfolios von Investitionsprojekten innerhalb eines Budgets zur Maximierung der Gesamtrendite.
- Produktionsplanung – Ermittlung von ganzzahligen Losgrößen über Zeitperioden hinweg, um Einrichtungs- und Lagerkosten auszugleichen.
- Netzwerkdesign – Auswahl, welche Verbindungen in einem Kommunikations- oder Transportnetzwerk installiert werden sollen.
So funktioniert es
So funktioniert es
Das Problem wird als mathematisches Programm formuliert: Entscheidungsvariablen definieren (die als ganzzahlig oder binär deklariert werden müssen, wo das Problem dies erfordert), eine lineare Zielfunktion zum Minimieren oder Maximieren schreiben und alle linearen Beschränkungen auflisten. Eine straffe Formulierung – eine, deren kontinuierliche (LP) Relaxation dem wahren ganzzahligen Optimum so nahe wie möglich kommt – reduziert die Lösungszeit dramatisch.
Die Ganzzahligkeitsbeschränkungen werden vorübergehend fallen gelassen, um die LP-Relaxation zu erhalten. Das Lösen dieser Relaxation ist schnell und liefert eine Schranke: Ihr Optimalwert ist immer mindestens so gut wie das wahre ganzzahlige Optimum (eine untere Schranke für die Minimierung). Wenn die Relaxationslösung zufällig ganzzahlig ist, ist das Problem gelöst. Andernfalls leitet die Lücke zwischen der Relaxation und der Ganzzahligkeit die Suche.
Eine gebrochenzahlige Variable in der Relaxationslösung wird ausgewählt und das Problem wird in zwei Teilprobleme aufgeteilt – eines, das verlangt, dass diese Variable abgerundet wird, und eines, das aufgerundet wird. Jedes Teilproblem wird selbst relaxiert und gelöst, wodurch ein Suchbaum entsteht. Zweige, deren Relaxationsschranke schlechter ist als die bisher gefundene beste ganzzahlige Lösung, werden ohne weitere Untersuchung abgeschnitten.
Schnittebenen sind gültige lineare Ungleichungen, die einen Teil des LP-Relaxations-Zulässigkeitsbereichs abschneiden, ohne einen ganzzahligen zulässigen Punkt zu entfernen. Das Hinzufügen starker Schnitte (Gomory-Schnitte, Cover-Ungleichungen, Clique-Schnitte) verschärft die LP-Schranke und reduziert die Anzahl der Knoten, die der Solver untersuchen muss.
Die beste ganzzahlige zulässige Lösung, die über alle untersuchten Knoten gefunden wird, wird als Optimum zurückgegeben. Die Optimalitätslücke – der prozentuale Unterschied zwischen der besten ganzzahligen Lösung und der besten verbleibenden Schranke – wird berichtet; eine Lücke von Null bescheinigt die globale Optimalität. Für große NP-schwere Instanzen kann der Solver frühzeitig mit einer vom Benutzer angegebenen Lückentoleranz beendet werden, wobei eine nahezu optimale Lösung mit einer nachweisbaren Schranke zurückgegeben wird.
Häufige Fallstricke
- Variablen als kontinuierlich zu deklarieren, wenn sie ganzzahlig sein sollten – oder umgekehrt – liefert stillschweigend falsche Lösungen; überprüfen Sie immer, ob die Variablentypen der physischen Realität des Problems entsprechen.
- Eine lose Formulierung mit einer großen LP-Relaxationslücke verursacht übermäßige Verzweigung; investieren Sie Zeit in die Verschärfung der Formulierung (starke Ungleichungen, Symmetriebrechung), bevor Sie mit der Lösung beginnen.
- Ignorieren der Ganzzahligkeitslücke in der Solver-Ausgabe: Ein berichteter Zielfunktionswert ist nur die beste gefundene ganzzahlige Lösung, nicht unbedingt das globale Optimum, es sei denn, die Lücke ist Null.
- Die Anwendung von IP auf Probleme, deren Zielfunktion oder Beschränkungen nichtlinear sind, ohne entsprechende MINLP-Behandlung führt zu falschen Modellen.
- Bei Planungs- oder Routenplanungsproblemen werden erhebliche Leistungsgewinne verschenkt, wenn gültige Ungleichungen (wie Clique- oder Cover-Schnitte) nicht hinzugefügt werden.
Häufig gestellte Fragen
Was ist der Unterschied zwischen IP und MIP?
Bei der reinen ganzzahligen Programmierung (IP) muss jede Entscheidungsvariable eine ganze Zahl sein. Bei der gemischt-ganzzahligen Programmierung (MIP) sind einige Variablen ganzzahlig oder binär, während andere kontinuierlich sein dürfen. MIP ist der allgemeinere und in der Praxis häufiger verwendete Rahmen, da die meisten realen Probleme diskrete Entscheidungen mit kontinuierlichen Mengen vermischen.
Warum ist ganzzahlige Programmierung NP-schwer, wenn lineare Programmierung polynomial ist?
Die lineare Programmierung optimiert über ein konvexes Polytop und kann mit dem Simplex- oder Interior-Point-Verfahren in Polynomialzeit gelöst werden. Das Hinzufügen von Ganzzahligkeitsbeschränkungen zerstört diese Konvexität: Die zulässige Menge wird zu einer endlichen, aber potenziell astronomisch großen Menge von ganzzahligen Punkten, und es ist kein Polynomialzeit-Algorithmus bekannt, der im Allgemeinen den besten findet. Die LP-Relaxation liefert eine Schranke, aber keine direkte Lösung.
Woher weiß ich, ob meine Lösung optimal ist?
Der Solver meldet eine Optimalitätslücke – den prozentualen Unterschied zwischen der besten gefundenen ganzzahligen Lösung und der besten verbleibenden unteren Schranke. Eine Lücke von 0 % bescheinigt die globale Optimalität. Bei großen Problemen können Sie eine Lückentoleranz (z. B. 1 %) festlegen und eine nahezu optimale Lösung akzeptieren; die Schranke garantiert immer noch, dass das wahre Optimum nicht mehr als dieser Prozentsatz besser sein kann.
Was macht eine 'straffe' Formulierung aus und warum ist sie wichtig?
Eine straffe Formulierung ist eine, deren LP-Relaxation eine Schranke nahe dem ganzzahligen Optimum liefert und eine kleine Ganzzahligkeitslücke hinterlässt. Wenn die Lücke klein ist, muss Branch-and-Bound weniger Knoten untersuchen und terminiert schneller. Das Hinzufügen gültiger Ungleichungen wie Gomory-Schnitte, Cover-Ungleichungen oder Clique-Schnitte verschärft die Formulierung und ist oft der wirkungsvollste Weg, einen Solver zu beschleunigen.
Verwandte Methoden
Quellen
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN: 9780471283669Kopiert.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN: 9780471359432Kopiert.