Branch-and-Cut

Branch-and-Cut ist das exakte Lösungsrahmenwerk für gemischt-ganzzahlige Programmierung (MIP), das jedem modernen kommerziellen und Open-Source-MIP-Solver zugrunde liegt. Es kombiniert zwei Ideen: (a) **Branch-and-Bound** — das ganzzahlige Problem durch Variablenverzweigung in kleinere Teilprobleme zerlegen, an jedem Knoten die LP-Relaxation lösen und Teilbäume verwerfen, deren LP-Schranke schlechter ist als die aktuell beste zulässige Lösung; (b) **Schnittebenen** — vor dem Verzweigen gültige Ungleichungen (Schnitte) hinzufügen, die von jeder ganzzahligen zulässigen Lösung erfüllt werden, aber das aktuelle fraktionale LP-Optimum abschneiden, wodurch die Relaxation enger und die Schranke besser wird. Der Ansatz wurde von Dantzig, Fulkerson und Johnson (1954) am Travelling Salesman Problem (TSP) eingeführt — sie verwendeten Subtour-Eliminationsschnitte innerhalb einer Branch-and-Bound-Suche und lösten eine 49-Städte-Instanz exakt. Padberg und Rinaldi (1991) verallgemeinerten das Rahmenwerk mit Separations-Routinen, die verletzte Schnitte im Flug erkennen. Heute ist Branch-and-Cut die Standardmethode für TSP, VRP, Scheduling, Standortwahl und Dutzende weitere kombinatorische Optimierungsprobleme; berichtete Solver-Leistung am TSP geht über 85K+ Knoten (Applegate, Bixby, Chvátal und Cook 2006). Praktisch eingesetzte Schnitte: Subtour-Elimination, Comb-Ungleichungen, Clique-Schnitte, Gomory-Schnitte, Mixed-Integer-Rounding-Schnitte, Lift-and-Project-Schnitte.