Eine Pricing-Heuristik mit <0,2 % Optimalitätslücke und bis zu 37 Mio. × Beschleunigung gegenüber dem Stand der Technik

Kapazitierte CPP-Variablen und Prioritätswarteschlangen-Constraint. Kunden werden in einer exogenen Reihenfolge verarbeitet (Ticket-Warteschlange, Ankunftszeit, Segment-Priorität, was die Anwendung verlangt). Die neue binäre y_inr zeigt an, ob Alternative i noch verfügbar ist, wenn Kunde n ankommt; die Constraint-Familie (f_inr, g_inr im Paper) sagt, dass y_inr in dem Moment auf 0 kippt, in dem die kumulierten Auswahlen von Alternative i ihre Kapazität c_i erreichen. Würde man die Prioritätswarteschlange durch eine globale Kapazitätsungleichung ersetzen, könnte der Solver Kunden endogen umpriorisieren, unrealistisch und die Umsatzvolatilität unterschätzend.

Was Kapazität kostet. Da ω jetzt wirklich binär ist, muss die Bilinearität p_i ω_inr mit Big-M-Hilfsvariablen linearisiert werden (das ursprüngliche MILP von Paneque et al.). Die QCQP-L-Reformulierung, die unsere unkapazitierte Arbeit getragen hat, gilt nicht mehr: Die LP-Relaxierung ist nicht ganzzahlig, also können wir ω nicht relaxieren. Übersetzung: Die gesamte algorithmische Kette aus pricing1 (räumliches B&B, B&BD, McCormick-Hüllen) kollabiert, und der einzige verbleibende exakte Ansatz ist das MILP, das empirisch bei R ≥ 50 ins Zeitlimit läuft.

Komplexität des kapazitierten BEA. Wir haben den BEA erweitert, indem wir sein inkrementelles Zielfunktions-Update durch einen Prioritätswarteschlangen-Allokations-Pass an den Blättern des Aufzählungsbaums ersetzt haben. Diese Korrektur erhält die Korrektheit, fügt aber pro Rekursionsebene einen NRJ-Faktor hinzu (wir müssen an jedem Breakpoint alle J Alternativen betrachten, nicht nur eine). Asymptotisch: immer noch polynomial in N und R, immer noch exponentiell in J, aber die Konstante davor ist signifikant schlechter als die unkapazitierte O(J!(NR)^J log NR)-Schranke.

Breakpoint Heuristic Algorithm: Koordinatenaufstieg über den Preisvektor, wobei jeder Schritt einen Ein-Preis-BEA löst (die Dimension, in der der BEA günstig ist, nur NR Breakpoints, kein Permutationsbaum). In Iteration t fixieren wir alle Preise ausser j(t), zählen die höchstens NR + 2 Kandidatenpreise für diese Koordinate unter dem aktuellen Warteschlangen-Status auf, werten die volle kapazitierte Zielfunktion an jedem Kandidaten aus und nehmen den besten. Wir zyklen die Dimensionen durch, bis J aufeinanderfolgende Koordinatenpässe keine Verbesserung bringen.

Effektive BHA-Komplexität. K ist die Anzahl äusserer Zyklen (empirisch 5–20 auf Benchmark-Instanzen), J die Koordinatenpässe pro Zyklus, NR die Breakpoint-Anzahl pro Koordinate, NRJ die Kosten einer Prioritätswarteschlangen-Auswertung. Der exponentielle-in-J-Term, der den exakten BEA-cap zerquetscht, ist weg, ersetzt durch eine quadratische-in-(NR)-Kosten, weshalb der BHA auf Instanzen skaliert, an die die exakte Methode nicht herankommt. Der Preis: kein Optimalitätszertifikat.

Iterated-Local-Search-Umschlag. Statt die Inkumbenten-Lösung nach jeder BHA-Terminierung zu mutieren (Lehrbuch-ILS), erweitern wir die Schrittweite und lassen die Liniensuche erneut laufen. Das ist der Perturbations-Operator: Wenn die lokale Suche die Klein-Schritt-Nachbarschaft erschöpft, springen wir in eine gröbere, erkunden erneut und akzeptieren bei Verbesserung. Wir machen weiter, bis δ Δ_max übersteigt. Empirisch schliesst das die verbleibende Lücke auf Benchmark-Instanzen, ILS trifft jedes bekannte Optimum dort, wo BHA ~0,04 % liegen lässt.

Heuristik-geführte exakte Methode. Wir geben die BHA-Lösung in unsere (unkapazitierte) räumliche Branch-and-Benders-Dekomposition als starke Anfangs-Unterschranke ein, und leiten daraus neue gültige Ungleichungen für die QCQP-L-Formulierung ab. Kombinierter Effekt auf die B&BD-Laufzeit, um 10 % Optimalitätslücke zu erreichen: bis 54 % Speed-up bei J = 4 (das Regime, in dem exakte Methoden noch möglich sind). Heuristik und exakte Methode helfen sich jetzt gegenseitig.