Gemischt-Ganzzahlige Lineare Programmierung (MILP)

Die gemischt-ganzzahlige lineare Programmierung (MILP) ist die Problemklasse min c^T x + d^T y s.t. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ in kanonischer Form, wobei x ∈ R^n stetige und y ∈ Z^p ganzzahlige Entscheidungsvariablen sind. Die Ganzzahligkeitsbedingung ist meist binär y ∈ {0,1}^p und modelliert logische Entscheidungen (investieren/nicht, Maschine an/aus, Route nutzen/nicht, Zuordnung Produkt-Lieferant-Periode). Fixkosten, diskrete Losgrößen, Disjunktionen und Big-M-Formulierungen erzwingen ganzzahlige Variablen. Komplexität: MILP ist NP-schwer (Cook 1971 via SAT-Reduktion; viele der 21 NP-vollständigen Probleme von Karp 1972 lassen sich als MILP formulieren); die LP-Relaxation (Ganzzahligkeit aufgehoben, durch y ≥ 0 ersetzt) ist polynomiell und liefert eine untere Schranke bei Minimierung. Der klassische Lösungsalgorithmus ist Branch-and-Bound nach Land und Doig (1960) — LP-Relaxation lösen, an einer fraktionalen y_i verzweigen und Teilbäume mit schlechterer Schranke beschneiden. Gomory (1958) führte fraktionale Schnitte ein, Padberg und Rinaldi (1991) entwickelten das Branch-and-Cut-Verfahren; moderne Löser kombinieren Schnittebenen (Gomory, Lift-and-Project, MIR, Cover), Knoten-Presolve, primale Heuristiken (Feasibility Pump, RINS), Konfliktanalyse und paralleles Branch-and-Bound. Praktische MILP-Modelle umfassen Standortwahl (Fixed Charge Facility Location), Tourenplanung, Produktionsplanung, Zuordnung, Packing, Netzdesign, Portfolioauswahl (Kardinalitätsrestriktionen) und Unit-Commitment in der Energiewirtschaft.